큰 문제를 작은 문제로 쪼개되, 한 번 푼 작은 문제의 답을 저장해 두고 재사용하는 기법 (Dynamic Programming, DP).
이름부터 — "동적"도 "계획법"도 오해를 부른다
1950년대 벨만이 붙인 이름으로, 기법의 내용과 별 관계가 없다. 연구비 심사를 통과하려고 그럴듯하게 지었다는 일화가 유명하다. 내용은 그냥 "중복 계산을 없애는 재귀" 다.
성립 조건 두 가지
① 최적 부분 구조 — 큰 문제의 최적해가 작은 문제의 최적해로 구성된다 ② 중복 부분 문제 — 같은 작은 문제가 여러 번 등장한다
②가 없으면 그냥 분할 정복이다. DP를 쓸 이유는 중복 때문이다.
피보나치로 보는 차이
단순 재귀 fib(5)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1) ← fib(2), fib(3)이 몇 번씩 반복된다
같은 계산을 반복하므로 O(2ⁿ) — n=50이면 우주가 끝나도 안 끝난다. 저장해 두면 각 값을 한 번만 계산하므로 O(n) 이다.
두 가지 방식
① 메모이제이션 (하향식, top-down)
long[] memo = new long[n + 1];
long fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; // 이미 풀었으면 꺼내 쓴다
return memo[n] = fib(n - 1) + fib(n - 2);
}
재귀 형태 그대로라 점화식을 옮기기 쉽다. 필요한 것만 계산한다. 단점은 재귀 깊이(스택 오버플로).
② 타뷸레이션 (상향식, bottom-up)
long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
작은 것부터 채워 올라간다. 재귀가 없어 스택 걱정이 없고 상수가 작다. 대신 안 쓰는 값까지 계산할 수 있다.
공간 최적화
피보나치는 직전 두 값만 필요하므로 배열이 필요 없다.
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long t = a + b; a = b; b = t; }
// 공간 O(n) → O(1)
2차원 DP도 직전 행만 쓰면 dp[2][m]으로 줄일 수 있다.
메모리 제한이 빡빡한 문제에서 자주 쓰는 기법이다.
대표 유형
| 문제 | 상태 정의 |
|---|---|
| 배낭 문제 | dp[i][w] = i번째까지 봤을 때 무게 w로 얻는 최대 가치 |
| 최장 공통 부분수열(LCS) | dp[i][j] = A의 i까지, B의 j까지의 LCS 길이 |
| 편집 거리 | dp[i][j] = A의 i까지를 B의 j까지로 바꾸는 최소 연산 |
| 동전 거스름돈 | dp[amount] = 그 금액을 만드는 최소 동전 수 |
DP의 90%는 "상태를 무엇으로 정의할 것인가" 다. 상태만 제대로 잡으면 점화식은 따라온다.
그리디와의 차이
그리디는 매 순간 최선을 골라 되돌아보지 않는다. 빠르지만 "지금 최선"이 "전체 최선"이 아닌 경우에 틀린다.
동전 [1, 3, 4]로 6원 만들기 그리디: 4 + 1 + 1 = 3개
- DP — : 3 + 3 = 2개 ✅ 그리디가 통하려면 별도의 증명이 필요하다. DP는 모든 경우를 보되 중복만 없애므로 항상 옳다.
실무에서
알고리즘 문제 밖에서도 원리는 같다 — 비싼 계산 결과를 저장해 재사용하는 것. 캐싱, 메모이제이션된 셀렉터(리액트), 증분 빌드 캐시, DB 실행계획 캐시가 모두 같은 발상이다.