동적 계획법(Dynamic Programming) / 분할 알고리즘(Divide and Conquer)

참조 :

syujisu.tistory.com/147

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 알고리즘

---

■ 동적 계획법(aka. DP)

1) 정의 :

입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

> 상향식 접근, 하위 해답에서 출발, 결과값 이용해 상위 문제 해결

> 하위 문제 해결과 상위 문제 해결 방식이 "동일" 할 때 유용

> Memoization으로 결과값을 중간저장하여 다시금 이용하게 함

> 재귀 점화식으로 구현되는 경우가 많음

   → 보통 문제를 "구현" 하는 방식 그 자체에 저장하는 경우가 많음

       stack, 2d-list map, dictionary 등

> 내글 참조

2021.03.19 - [알고리즘] - Dynamic Programming( 동적계획법 )

 

 

■ 분할 알고리즘

1) 정의 :

문제를 나눌 수 없을 부분까지 먼저 나눈 후, 하위의 해답을 stack의 return으로 받으며 최종 답을 도출

> 문제 자체가 중복되지 않음(완전 개별 문제들로 나눠서 해결)

> 재귀 점화식으로 구현되는 경우가 많음