Concept
-
하나의 큰 문제를 작은 Subproblem으로 나누고 각각의 해결 결과를 저장해놓고, 문제를 반복해서 풀이 않도록 하는 것
→ Avoid re-computation via reuse
DP 적용 조건 (and 조건)
- Optimal Substructure
- problem의 최적해가 subproblem의 최적해로 구성될 수 있어야 한다. (전체를 푸는 방법은 부분을 푸는 방법 위에 있다)
- 예를 들어, 다익스트라 처럼, A to B까지의 최단 경로 + B to C 까지의 최단 경로가 A to C까지의 최단 경로가 될 수 있는 구조
- Overlapping Subproblems
- 동일한 subproblem 문제를 반복해서 계산하는 재귀적인 구조여야 함
- (이건 와닿지가 않네. 재귀 구조로 계속해서 함수를 호출하는 형태면 다 똑같은거 아닌가? 일단 넘어가고)
주요 전략
- Memorization (Top-down)
- 재귀 함수 기반
- 계산 결과를 cache(Memory)에 저장해놓고, 호출될 때 계산된 결과 있으면 그거로 활용
- Tabulation (Bottom-up)
- 작은 문제부터 차근차근 해답을 구함 → 일반적으로 Sub-loop처럼 푸는 듯? (loop문은 캐시 효율 좋지)
-
-
공간 최적화해야함
- 모든 배열 값을 저장할 필요는 없음. 단순 연산으로 다음 결과를 구할 수 있다면 앞에 값만 알면 되겠지?
-
대표적인 예시
- 피보나치 수열 : 가장 기본적인 DP 예시
- 최단 경로 : 오른쪽 or 아래로만 움지여서 도착하는 경우의 수
- 최적화_ 0/1 Knapsack Problem : 배낭에 넣을 물건 선택
- 문자열_ Longest Common Subsequence(LCS) : 두 문자열에서 가장 큰 공통 부분 찾는거
- 분할 정복_ Matrix Chain Multiplication : 행렬 곱의 최소 연산 횟수
- 기타 Advanced 기법
- DP with Bit-masking, Digit DP, DP on Trees/Graphs, Convex Hull Trick/Monotonic Queue Optimization 등