**동적 계획법(Dynamic Programming, DP)**은 복잡한 문제를 작은 부분 문제들로 나눈 후, 그 부분 문제의 해를 메모리에 저장하여 동일한 계산의 중복을 방지하는 최적화 기법입니다.
1. DP 적용을 위한 2가지 핵심 조건
- 중복되는 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 반복해서 나타남.
- 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 도출할 수 있음.
2. Top-Down(하향식) vs Bottom-Up(상향식)
| 방식 | 설명 | 주요 기술 |
|---|---|---|
| Top-Down (하향식) | 큰 문제를 해결하기 위해 재귀적으로 작은 문제를 호출 | 메모이제이션 (Memoization) |
| Bottom-Up (상향식) | 가장 작은 부분 문제부터 차례대로 반복문으로 계산하여 테이블에 채워나감 | 타뷸레이션 (Tabulation) |
3. 피보나치 수열 비교 예시
# Bottom-Up (Tabulation) DP 방식 - O(N) 시간, O(N) 공간
def fibo_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibo_dp(10)) # 55
4. DP의 대표 문제
- 최장 공통 부분 순서 (LCS, Longest Common Subsequence): 두 문자열 간 가장 긴 공통 부분 수열 길이 구하기.
- 0/1 배낭 문제 (Knapsack Problem): 담을 수 있는 최대 무게 한도 내에서 가치의 합이 최대가 되도록 물건을 선택하는 문제 ($O(N imes W)$).
5. 자주 묻는 질문 (Q&A)
Q. 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 중 무엇이 더 유리한가요? A. 메모이제이션은 필요한 부분 문제만 계산하므로 가끔 효율적일 수 있으나 재귀 오버헤드(스택 오버플로 위험)가 존재합니다. 타뷸레이션은 반복문을 사용하므로 오버헤드가 적고 공간 복잡도를 최적화하기에 용이합니다.