D&C와 DP - divide and conquer(분할정복 방식), dynamic programming(동적 프로그래밍)
1. Divide-and-Conquer
- 분할(divide)
해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.
- 정복(Conquer - Solve)
나눈 작은 문제를 각각 해결한다.
- 통합(Combine - Obtain the solution)
필요하다면 해결된 해답을 모은다.
- Top-down approach(하향식 해결법)
나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다
ex) merge sort
merge sort는 배열을 쪼갰을 때 쪼갠 배열 간에 상관관계가 없다.
하지만 DP(Bottom-up)의 예시인 피보나치 수열은 앞선 2개의 값을 더해서 함수값을 구한다. 다시 말해, 나누어진 부분들(f(2), f(3), f(4)...) 사이에 서로 연관이 있다.
- D&C는 같은 항을 한 번 이상 계산하므로 비효율적인 계산 방법이다. 따라서 피보나치 수열에는 적합하지 않다.
2. Dynamic programming
- 작은 문제를 먼저 해결하고 그 결과를 저장한 다음, 나중에 필요할 때 꺼내서 쓴다.
- Bottom-Up approach(상향식 해결법)
ex) 피보나치 수열
f(n) = f(n-2) + f(n-1)
DP에 의한 설계 절차
- 문제의 입력에 대해서 최적의 해답을 주는 recursive property 설정
- 상향적으로 최적의 해답을 계산
- 상향적으로 최적의 해답을 구축
3. 비교 - divide and conquer와 Dynamic programming의 공통점
- 하나의 문제를 작은 문제로 쪼갠다.
- 전체 문제와 부분 문제를 똑같은 방법으로 푼다.
