1. 동적 계획법 (Dynamic Programming, 다이내믹 프로그래밍) 전략
ㅇ 중첩된 부 문제들을 갖는 복잡한 문제를, 효율적으로 해결하는, 최적화 기법
- 하위 문제의 해를 저장하여 중복 계산을 피하고,
- 전체 문제를 해결하는 상향식 접근 방식을 취함
※ 1953년 미국 응용수학자 리처드 벨먼 (Richard Ernest Bellman, 1920~1984) 에 의해 고안됨
※ 분할 정복, 동적 계획 방법 간의 비교
- 분할 정복 : 분할된 부 문제들이 서로 독립적임
- 동적 계획 : 분할된 부 문제들이 서로 의존적임
2. 동적 계획법의 주요 특징
ㅇ 분할된 부 문제들이 서로 독립일 필요 없음
- 특히, 주어진 문제가 재사용 가능한 여러 중복된 부 문제들로 중첩되면, 유리함
ㅇ 동일한 부 문제가 여럿 나타날 경우, 중복 계산의 방지를 위해, 결과를 저장하여 재사용함
ㅇ 한 번 계산한 결과를 테이블(Table) 또는 배열(Array) 형태로 저장 (시간 절약)
3. 동적 계획법의 적용 대상
ㅇ 주어진 문제가,
- 최적 부분 구조 (Optimal Substructure)를 갖고,
. 전체 문제의 최적 해가 하위 문제들의 최적 해들로 구성될 수 있음.
. 例) 최단 경로, 최소 비용 문제 등
- 부 문제들이 중첩되는 (Overlapping Subproblem) 정도가 높을 때, 유용함
. 동일한 부 문제가 여러 번 재사용됨
. 例) 피보나치 수열, 배낭 문제 등
※ 최적성의 원리
- "어떤 문제의 최적 해는, 그 문제의 하위 문제들의 최적 해들로부터 구성될 수 있다"는 원리
※ 대표적인 동적 계획법 문제 例)
- 수열 : 피보나치 수열, LIS(최장 증가 부분 수열)
- 경로 : 최단 경로 (Floyd, Bellman-Ford)
- 최적화 : 배낭 문제(Knapsack Problem), 동전 거스름돈 문제
- 문자열 : 편집 거리(Levenshtein Distance), LCS(최장 공통 부분 수열)
4. 동적 계획법의 풀이 개요
ㅇ 문제를 하위 문제들로 분할하고,
ㅇ 간단한 하위 문제부터 해결하면서,
ㅇ 각 하위 문제의 해를 테이블에 저장해 놓고,
ㅇ 저장된 해를 이용해 더 복잡한 상위 문제를 해결하며,
ㅇ 최종적으로 전체 문제의 해를 도출
5. 동적 계획법의 풀이 요점
ㅇ 재귀 관계식(Recurrence Relation)을 세워, 문제를 더 작은 부분으로 분할
ㅇ 언뜻 재귀 처럼 보이지만, 실제 구현은 보통 상향식(Bottom-up)임
ㅇ 각 부 문제의 결과를 한 번만 계산하고 저장 (효율적)
ㅇ 나중에 동일한 부 문제가 나오면, 저장된 결과를 그대로 재사용
6. 동적 계획법의 구현 방식
ㅇ Memoization (메모이제이션) (하향식 접근 풀이, Top-down)
- 재귀 호출을 사용하되, 이미 계산한 값을 캐시에 저장하여 재사용
ㅇ Tabulation (상향식 접근 풀이, Bottom-up)
- 작은 문제부터 차례대로 해를 계산하고, 테이블에 채워나감
7. DP 테이블 (Dynamic Programming Table), DP 배열 (DP Array)
ㅇ 동적 계획법에서,
- 중간 계산 결과를 저장하는 테이블 (배열 혹은 행렬)
- 하위 문제의 해를 재사용하기 위한 핵심 도구
ㅇ 형태 : 통상, 1차원 또는 2차원 배열 형태
- 문제의 구조에 따라 크기와 차원이 달라짐
- 例) dp[i] (1차원), dp[i][j] (2차원)
ㅇ 역할
- 각 셀(cell)은, 특정 부 문제의 해를 의미
- 이전 셀 값들을 이용해 새로운 값을 계산함
- 계산 순서를 체계적으로 관리함으로써, 재귀 호출의 중복을 제거함
ㅇ 例) 피보나치 수열 : F(n) = F(n-1) + F(n-2)
[# \begin{array}{c|cccccc} n & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline
F(n) & 0 & 1 & 1 & 2 & 3 & 5 \end{array} #]
- (1차원 DP 테이블) dp[n] = dp[n-1] + dp[n-2]
- (상향식) 작은 n부터 시작
- (중간 계산 저장 활용) 각 항은 이전에 계산,저장된 두 항의 값들로 계산됨