분할 정복 vs 동적계획법

분할 정복(Divde and Qonquer) 와 동적계획법 (Dynamic Programming, DP) 은 모두 복잡한 문제를 해결하기 위해 그 문제를 더 작은 하위 문제로 나누는 기법으로 비슷해 보일 수 있다.

두 알고리즘의 차이점은 다음과 같다.

분할정복

• 문제 분할 : 문제를 가능한 한 독립적이고 비슷한 크기의 더 작은 하위 문제로 나눈다.
• 하위 문제의 중복여부 : 분할 정복에서 각 하위 문제는 독립적이며, 중복되는 하위 문제가 발생하지 않는다.
  • 예) 병합 정렬(Merge Sort) , 퀵정렬

동적 계획법

• 문제 분할 : 문제를 더 작은 하위문제로 나누지만, 이때 나누어진 하위 문제들 사이에는 중복이 발생할 수 있다.
• 하위 문제의 중복여부 : 하위 문제들이 중복될수 있기 때문에, 그 결과를 저장(메모이제이션) 하여 필요할때마다 재사용 한다.
  • 예) 피보나치 수열, 최장 공통 부분 수열 (LCS) , 0-1 배낭 문제(Knapsack Problem)