동적 계획법 (DP, 메모이제이션, 점화식)
알고리즘을 배우다 가장 큰 학습 벽으로 자주 꼽히는 영역이 동적 계획법(DP, Dynamic Programming)이다. 분할 정복이 큰 문제를 작은 문제로 쪼개되 작은 문제들이 서로 독립적인 경우에 잘 동작했다면, DP는 작은 문제들이 서로 겹치는 경우를 다룬다. 같은 부분 문제를 한 번만 풀고 그 답을 저장(메모)해 두면 다음에 만났을 때 즉시 꺼낼 수 있고, 이 단순한 발상의 전환이 지수 시간 알고리즘을 다항 시간으로 끌어내린다. 본 글은 DP의 두 가지 조건, 메모이제이션과 타뷸레이션의 차이, 그리고 고전 응용을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 15장). 제가 학교 알고리즘 시간에 피보나치를 단순 재귀로 짰을 때 n=40에서 몇 초가 걸리던 코드가 memo 한 줄 추가로 즉시 끝나는 모습을 본 후로는 "DP는 알고리즘이 아니라 사고의 전환"이라는 인상을 손끝으로 받아들였다.
DP의 두 가지 조건 — 최적 부분 구조와 중복 부분 문제
어떤 문제에 DP를 적용할 수 있는지를 판단하는 두 가지 표준 조건이 있다. 시험에서 자주 출제되는 항목이다.
| 조건 | 의미 | 예시 |
|---|---|---|
| 최적 부분 구조 (Optimal Substructure) | 작은 문제의 최적해를 결합해 큰 문제의 최적해를 만들 수 있다 | 최단 경로, 최장 공통 부분 수열 |
| 중복 부분 문제 (Overlapping Subproblems) | 같은 부분 문제가 여러 번 등장한다 | 피보나치, 0-1 배낭 |
여기서 최적 부분 구조란 한 큰 문제의 최적해가 그 안의 작은 부분 문제들의 최적해로 구성된다는 성질을 가리키며, 이 성질이 없으면 DP 자체가 성립하지 않는다. 두 조건이 동시에 만족될 때 DP가 위력을 발휘한다. 예를 들어 피보나치 수열은 F(n) = F(n-1) + F(n-2)로 두 조건을 모두 만족하지만, 분할 정복으로 푸는 병합 정렬은 부분 문제가 서로 겹치지 않아 DP가 의미 없다.
DP 풀이는 두 가지 방식으로 구현된다. 두 방식의 차이는 거의 모든 시험 답안에서 묻는 핵심 포인트다.
| 방식 | 방향 | 구현 | 메모리 |
|---|---|---|---|
| 메모이제이션 (Memoization, Top-Down) | 큰 문제 → 작은 문제 (재귀) | 재귀 + 캐시 | 호출 스택 + 캐시 |
| 타뷸레이션 (Tabulation, Bottom-Up) | 작은 문제 → 큰 문제 (반복) | 반복문 + 배열 | 배열만 |
여기서 메모이제이션(memoization)이란 함수의 호출 결과를 캐시에 저장해 같은 인자로 다시 호출될 때 재계산 없이 즉시 반환하는 기법을 가리키며, 재귀의 직관성을 유지하면서 중복 계산을 제거한다. 타뷸레이션은 같은 일을 반복문으로 처리해 호출 스택 비용을 없앤 형태이며, 일반적으로 메모리·속도 모두에서 약간 우월하지만 코드 가독성은 떨어진다.
# 1) 메모이제이션 — 재귀 + 캐시
def fib_memo(n, memo={}):
if n < 2: return n
if n in memo: return memo[n]
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
# 2) 타뷸레이션 — 반복문 + 배열
def fib_tab(n):
if n < 2: 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]
# 3) 공간 최적화 — 직전 두 값만 유지
def fib_opt(n):
if n < 2: return n
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b
# 시간복잡도: 모두 O(n) — 단순 재귀(O(2^n))와 비교해 압도적n = 40에서 단순 재귀는 1초 넘게 걸리지만 위 세 방식은 마이크로초 단위로 끝난다. 솔직히 제 경험상 학교 알고리즘 과제에서 처음 이 차이를 직접 측정해 본 후로는 "DP는 단순한 시험 토픽이 아니라 같은 문제의 시간 차원 자체를 바꾸는 도구"라는 인상을 받아들였다.
DP 점화식 설계의 표준 절차
DP 문제를 푸는 가장 큰 어려움은 코드가 아니라 점화식(recurrence)을 세우는 일이다. 점화식만 정확히 잡히면 그 뒤 코드는 거의 자동으로 흘러나온다. DP 점화식 설계의 표준 5단계는 다음과 같다.
- 상태(State) 정의 — dp[i] 또는 dp[i][j]가 무엇을 의미하는지 한 줄로 명시
- 기저 조건(Base Case) — 가장 작은 입력에 대한 답을 직접 정의
- 점화식(Transition) — dp[i]를 더 작은 dp 값들로 표현
- 계산 순서 — Bottom-Up이면 어느 방향으로 채울지, Top-Down이면 어디서 시작할지
- 답의 위치 — 최종 답이 dp의 어느 칸에 있는지
대표적인 DP 고전 문제 네 가지를 표로 정리하면 다음과 같다(출처: 위키백과 — Dynamic programming).
| 문제 | 상태 정의 | 점화식 | 시간 |
|---|---|---|---|
| 피보나치 | dp[i] = i번째 피보나치 수 | dp[i] = dp[i-1] + dp[i-2] | O(n) |
| 0-1 배낭 | dp[i][w] = i개 물건·용량 w일 때 최대 가치 | dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) | O(nW) |
| LIS (최장 증가 부분 수열) | dp[i] = i로 끝나는 LIS 길이 | dp[i] = max(dp[j] + 1) for j < i, a[j] < a[i] | O(n²) → O(n log n) |
| LCS (최장 공통 부분 수열) | dp[i][j] = a[:i], b[:j]의 LCS 길이 | a[i]=b[j]면 dp[i-1][j-1]+1, 아니면 max(dp[i-1][j], dp[i][j-1]) | O(nm) |
# 0-1 배낭 (Knapsack) — DP의 가장 고전적인 예
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if weights[i-1] <= w:
dp[i][w] = max(
dp[i-1][w], # i번 물건 안 담음
dp[i-1][w - weights[i-1]] + values[i-1] # i번 물건 담음
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5)) # 7 (2+3 또는 5)여기서 0-1 배낭이란 각 물건을 한 번만 통째로 담거나(0/1) 담지 않는 조건에서 무게 한도 안에 최대 가치를 채우는 문제를 가리키며, 자원 할당·투자 결정·운송 적재처럼 일상의 자원 분배 문제의 대표적인 추상 모델이다.
DP의 실전 응용과 한계
DP가 빛을 발하는 영역은 매우 광범위하다. 첫째, 편집 거리(Edit Distance, Levenshtein) — 두 문자열을 같게 만들기 위한 최소 삽입·삭제·교체 횟수. 맞춤법 검사·DNA 시퀀스 비교·git diff의 토대이다. 둘째, 동전 거스름돈 — 주어진 금액을 최소 동전 수로 만드는 문제. 그리디로는 일반적으로 최적이 보장되지 않지만 DP로는 항상 최적이다. 셋째, 행렬 체인 곱셈 — 여러 행렬을 곱하는 순서를 정해 곱셈 횟수를 최소화. 넷째, 외판원 문제(TSP)의 비트마스크 DP — 도시 순회의 최소 비용. 다섯째, 트리 DP·구간 DP — 트리나 구간 구조 위에서 동작하는 DP 변형으로, 경쟁 프로그래밍에서 가장 자주 등장한다.
DP에도 한계가 있다. 첫째, 상태 공간이 너무 크면 메모리가 폭발한다. 0-1 배낭의 dp[n][W]는 W가 10^9이면 사실상 불가능하다. 둘째, 부분 문제가 겹치지 않으면 DP가 무의미하다. 이 경우 분할 정복·그리디·완전 탐색이 더 적합하다. 셋째, 상태 정의를 잘못 잡으면 점화식이 안 풀린다. 같은 문제도 dp[i]를 어떻게 정의하느냐에 따라 O(n)에 풀리거나 영원히 안 풀리는 일이 흔하다. 솔직히 이건 예상 밖이었는데, 학교 알고리즘 시험에서 가장 자주 틀린 문제가 정확히 "상태 정의" 한 줄을 잘못 잡은 경우였고, 점화식이 안 풀린다 싶을 때마다 상태 정의부터 다시 보는 습관이 자리 잡혔다.
마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "동적 계획법(DP)은 최적 부분 구조와 중복 부분 문제를 가진 문제에서 작은 문제의 답을 저장해 두고 재사용하는 알고리즘 패러다임이다. 구현은 메모이제이션(top-down 재귀+캐시)과 타뷸레이션(bottom-up 반복+배열) 두 방식이 있으며, 피보나치·0-1 배낭·LIS·LCS·편집 거리가 대표 응용이다"는 두 문장이 표준 답안 표현으로 통한다. 다음 글에서는 DP와 달리 매 단계 즉시 결정을 내리는 그리디 알고리즘을 이어서 다룬다.
메타 디스크립션: 동적 계획법(DP)의 두 조건(최적 부분 구조·중복 부분 문제), 메모이제이션과 타뷸레이션의 차이, 점화식 설계 5단계, 그리고 피보나치·0-1 배낭·LIS·LCS 같은 고전 응용을 알고리즘 입문자 관점에서 세심하게 정리합니다.