동적계획법(Dynamic Programming)

• 복잡한 문제를 "재귀"를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법

• 어떤 문제가 최적 부분 구조(optimal substructure)와 중복되는 부분 문제(overlapping subproblem)를 갖고 있다면, 동적 계획법으로 해결할 수 있음

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

• 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식

• memoization 기법을 사용함

최적 부분 구조

답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조

동적 계획법을 사용하려면
1. 먼저 최적 부분 구조가 있는지 확인
2. 부분 문제를 풀고 결과를 저장한 후, 다음 부분 문제(중복되는 부분 문제)를 푸는 과정에서 저장된 결과를 사용

메모이제이션(memoization)

• 프로그램이 동일한 계산을 반복할 때,
  이전에 계산한 값을 메모리에 저장하여
  동일한 계산의 반복 수행을 제거하여 프로그램의 실행속도를 빠르게 하는 기법
  동적 계획법의 핵심!
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용 됨 (예: 피보나치 수열)

파이썬과 같은 고급 언어는
반환 값을 캐싱하여 재귀식을 직접 구현할 수 있음!

분할 정복 (divide and conquer)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되지 않음 (예: 병합 정렬, 퀵 정렬 등)

동적 계획법 vs. 분할 정복

• 공통점
  * 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  * 동적 계획법: 부분 문제는 중복되어 상위 문제해결 시 재활용 됨. memoization사용(부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  • 분할 정복: 부분 문제는 서로 중복되지 않음, memoization 사용 안함

Reference

• [책] 파이썬 자료구조와 알고리즘