다이나믹 프로그래밍이란?
다이나믹 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 하위 문제로 나누어 풀되, 같은 하위 문제를 반복 계산하지 않고 저장해두고 재사용하는 알고리즘 설계 기법입니다.
"이미 계산한 건 다시 계산하지 않는다"는 단순한 아이디어지만, 이것만으로 시간복잡도를 극적으로 줄일 수 있습니다.
피보나치 수열: DP를 이해하는 가장 좋은 예제
피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다.
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
방법 1: 단순 재귀 — O(2^n)
F(n)을 구하기 위해 F(n-1)과 F(n-2)를 각각 재귀 호출하면, 같은 값을 수십 번 반복 계산합니다.
F(5)를 구하려면 F(3)이 2번, F(2)가 3번 호출됩니다. n이 커지면 호출 횟수가 기하급수적으로 증가하여 O(2^n)이 됩니다.
이것이 바로 DP가 해결하는 문제입니다.
방법 2: 메모이제이션 (Top-Down) — O(n)
한 번 계산한 결과를 배열이나 해시맵에 저장해두고, 같은 입력이 들어오면 저장된 값을 반환합니다.
핵심 아이디어:
- •F(n)을 처음 계산하면 결과를 memo[n]에 저장
- •다음에 F(n)이 필요하면 memo[n]을 바로 반환
- •재귀 구조는 유지하되, 중복 계산을 제거
이렇게 하면 각 F(i)를 딱 한 번만 계산하므로 O(n)이 됩니다.
방법 3: 타뷸레이션 (Bottom-Up) — O(n)
작은 문제부터 차례대로 풀어 올라가는 방식입니다. 재귀 대신 반복문을 사용합니다.
핵심 아이디어:
- •dp[0] = 0, dp[1] = 1부터 시작
- •dp[2] = dp[0] + dp[1], dp[3] = dp[1] + dp[2], ...
- •반복문으로 dp[n]까지 순서대로 채움
메모이제이션과 시간복잡도는 같지만, 재귀 호출 오버헤드가 없고 스택 오버플로우 위험이 없습니다.
세 가지 방법 비교
| 방법 | 시간복잡도 | 공간복잡도 | 특징 |
|---|---|---|---|
| 단순 재귀 | O(2^n) | O(n) 스택 | 중복 계산 심각 |
| 메모이제이션 | O(n) | O(n) | Top-Down, 직관적 |
| 타뷸레이션 | O(n) | O(n) → O(1) 최적화 가능 | Bottom-Up, 안정적 |
DP를 적용할 수 있는 조건
1. 최적 부분 구조 (Optimal Substructure)
큰 문제의 최적 해가 작은 문제의 최적 해로 구성될 수 있어야 합니다.
2. 중복되는 하위 문제 (Overlapping Subproblems)
같은 하위 문제가 여러 번 반복되어야 합니다. 반복이 없다면 분할 정복으로 충분합니다.
피보나치 이후의 DP 문제들
피보나치를 이해했다면 다음 문제들에 도전해보세요.
동전 교환 — 주어진 동전으로 특정 금액을 만드는 최소 동전 수
0/1 배낭 문제 — 무게 제한 안에서 가치를 최대화하는 물건 조합
LCS — 두 문자열의 최장 공통 부분 수열
알고노트에서 직접 확인하세요
재귀 호출이 어떻게 중복되는지, 메모이제이션이 어떻게 중복을 제거하는지, 알고노트에서 피보나치의 재귀 트리를 시각적으로 확인할 수 있습니다. DP의 핵심을 눈으로 이해하세요.