C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
![C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]](/og/s/cpp-series-54-4-dynamic-programming.webp)
이 글의 핵심
C++ DP 마스터: 피보나치, 배낭 문제, LCS, 최장 증가 부분 수열, 공간 최적화. 문제 시나리오, 완전한 예제, 흔한 실수, 프로덕션 패턴. 동적 계획법(DP)을 모르면 재귀만으로는 해결 불가능한 문제를 마주합니다. 비유하면 "같은 계산을 수천 번 반복하는 것"과 "한 번 계산한 결과를 재사용하는 것"의 차이입니다. 시나리오: 피보나치 수열 fib(n)을 재귀로 구현했더니,.
들어가며: “fib(40)이 10초나 걸려요”
실제 겪는 문제 시나리오
동적 계획법(DP)을 모르면 재귀만으로는 해결 불가능한 문제를 마주합니다. 비유하면 “같은 계산을 수천 번 반복하는 것”과 “한 번 계산한 결과를 재사용하는 것”의 차이입니다.
시나리오: 피보나치 수열 fib(n)을 재귀로 구현했더니, n=40에서 10초 이상 걸립니다.
flowchart TD
subgraph wrong["❌ 순수 재귀 O(2^n)"]
W1[fib(40)] --> W2[fib(39) + fib(38)]
W2 --> W3[중복 계산 수천만 번]
W3 --> W4[10초 이상]
end
subgraph right["✅ DP 메모이제이션 O(n)"]
R1[fib(40)] --> R2[이미 계산된 값 재사용]
R2 --> R3[40번 계산]
R3 --> R4[마이크로초 단위]
end
이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 완전한 DP 예제(피보나치, 배낭, LCS, LIS), 자주 하는 실수, 최적화 패턴, 프로덕션에서 쓰는 패턴까지 단계별로 다룹니다.
이 글을 읽으면:
- DP의 핵심 개념(메모이제이션, 타뷸레이션)을 이해할 수 있습니다.
- 실전 문제에 DP를 적용할 수 있습니다.
- 공간·시간 최적화를 적용할 수 있습니다.
요구 환경: C++17 이상
목차
1. 문제 시나리오
시나리오 1: 피보나치 수열이 너무 느림
상황: fib(n)을 재귀로 구현했는데, n=40에서 10초 이상 걸립니다.
원인: fib(40)은 fib(39)와 fib(38)을 호출하고, 각각이 다시 하위 값을 호출합니다. 같은 fib(k)가 수천 번 중복 계산됩니다.
해결: 메모이제이션 또는 타뷸레이션으로 한 번 계산한 값을 저장해 재사용합니다.
시나리오 2: 배낭 문제 - 물건 선택 최적화
상황: 한정된 용량의 배낭에 가치를 최대화하도록 물건을 넣어야 합니다.
원인: 각 물건을 넣거나 넣지 않거나의 2^n 가지 경우의 수. 브루트포스는 n=30만 되어도 10억 가지 이상입니다.
해결: DP로 dp[i][w] = “i번째 물건까지 고려했을 때 용량 w에서의 최대 가치”를 채워 나갑니다.
시나리오 3: 두 문자열의 최장 공통 부분 수열(LCS)
상황: DNA 서열 비교, diff 알고리즘, 버전 관리에서 두 시퀀스의 공통 부분을 찾아야 합니다.
원인: 모든 부분 수열을 나열하면 2^n × 2^m. n=m=20만 되어도 수조 가지입니다.
해결: DP로 dp[i][j] = “s1[0..i]와 s2[0..j]의 LCS 길이”를 채웁니다.
시나리오 4: 최장 증가 부분 수열(LIS)
상황: 주가 추이, 시퀀스 데이터에서 가장 긴 증가하는 부분을 찾아야 합니다.
원인: 모든 부분 수열을 검사하면 2^n. n=100이면 불가능합니다.
해결: DP O(n²) 또는 이진 탐색 활용 O(n log n)으로 해결합니다.
시나리오 5: 편집 거리 (Levenshtein Distance)
상황: 오타 수정, DNA 변이 분석, 검색 제안에서 두 문자열을 같게 만들기 위한 최소 편집 횟수가 필요합니다.
원인: 삽입/삭제/치환의 모든 조합을 탐색하면 3^(n+m) 수준입니다.
해결: DP로 dp[i][j] = “s1[0..i]를 s2[0..j]로 만드는 최소 편집 횟수”를 채웁니다.
시나리오 6: 코딩 테스트에서 시간 초과
상황: 재귀 또는 브루트포스로 풀었더니 n=100에서 시간 초과(TLE)가 발생합니다.
원인: 문제에 최적 부분 구조와 중복 부분 문제가 있는데 DP를 적용하지 않았습니다.
해결: “이전 상태만으로 현재 상태를 결정할 수 있는가?”를 묻고, 그렇다면 DP를 의심합니다.
시나리오 7: DNA 시퀀스 정렬 (편집 거리 활용)
상황: 생물정보학에서 두 DNA 서열의 유사도를 측정해 변이(mutation)를 분석해야 합니다.
원인: 삽입·삭제·치환의 모든 조합을 탐색하면 3^(n+m) 수준으로 계산 불가능합니다.
해결: 편집 거리(Levenshtein) DP로 O(n×m)에 최소 편집 횟수를 구하고, 유사도 점수를 도출합니다.
시나리오 8: 주식 포트폴리오 최적화
상황: 여러 주식의 가격 시계열에서 “가장 긴 상승 구간”을 찾아 트렌드를 분석해야 합니다.
원인: 모든 부분 수열을 검사하면 2^n. n=1000이면 현실적으로 불가능합니다.
해결: LIS(최장 증가 부분 수열) DP O(n²) 또는 이진 탐색 O(n log n)으로 효율적으로 해결합니다.
DP 적용 여부 판단 플로우차트
flowchart TD
A[최적화/계산 문제] --> B{이전 상태만으로\n현재 상태 결정 가능?}
B -->|예| C{같은 부분 문제가\n여러 번 등장?}
B -->|아니오| D[그리디/분할정복 검토]
C -->|예| E[✅ DP 적용]
C -->|아니오| F[분할정복 검토]
E --> G[점화식 세우기]
G --> H[초기값 설정]
H --> I[메모이제이션 또는 타뷸레이션]
2. 기본 개념: 메모이제이션 vs 타뷸레이션
2.1 DP의 핵심 원리
동적 계획법은 최적 부분 구조(optimal substructure)와 중복 부분 문제(overlapping subproblems)가 있을 때 적용합니다.
flowchart LR A[최적 부분 구조] --> B[큰 문제의 최적해 = 작은 문제들의 최적해 조합] C[중복 부분 문제] --> D[같은 부분 문제가 여러 번 등장] B --> E[DP 적용 가능] D --> E
| 접근법 | 설명 | 방향 | 장점 |
|---|---|---|---|
| 메모이제이션 | 재귀 + 캐시 | Top-Down | 직관적, 필요한 부분만 계산 |
| 타뷸레이션 | 반복 + 테이블 | Bottom-Up | 스택 오버플로우 없음, 캐시 친화적 |
2.2 메모이제이션 (Top-Down)
재귀 호출 시 이미 계산한 결과를 캐시에 저장하고, 같은 입력이 오면 캐시에서 반환합니다.
#include <vector>
#include <unordered_map>
// 피보나치 - 메모이제이션
// 시간: O(n), 공간: O(n) + 재귀 스택
long long fib_memo(int n, std::vector<long long>& cache) {
if (n <= 1) return n;
if (cache[n] != -1) return cache[n]; // 이미 계산됨
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
return cache[n];
}
long long fib(int n) {
std::vector<long long> cache(n + 1, -1);
return fib_memo(n, cache);
}2.3 타뷸레이션 (Bottom-Up)
작은 문제부터 순서대로 테이블을 채워 나가며, 큰 문제의 해를 구합니다.
// 피보나치 - 타뷸레이션
// 시간: O(n), 공간: O(n)
long long fib_tab(int n) {
if (n <= 1) return n;
std::vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}3. 완전한 DP 예제
3.1 피보나치: 브루트포스 → DP
문제: fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1
브루트포스 (절대 사용 금지):
// ❌ O(2^n) - n=40에서 수천만 번 호출
long long fib_naive(int n) {
if (n <= 1) return n;
return fib_naive(n - 1) + fib_naive(n - 2);
}DP 타뷸레이션 (권장):
// ✅ O(n) 시간, O(n) 공간
long long fib_dp(int n) {
if (n <= 1) return n;
std::vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}공간 최적화 (O(1) 공간):
// ✅ O(n) 시간, O(1) 공간 - 이전 2개만 필요
long long fib_optimized(int n) {
if (n <= 1) return n;
long long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; ++i) {
long long curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}| 방법 | 시간 | 공간 | n=40 기준 |
|---|---|---|---|
| 브루트포스 | O(2^n) | O(n) 스택 | ~10초 |
| 메모이제이션 | O(n) | O(n) | ~1ms |
| 타뷸레이션 | O(n) | O(n) | ~1ms |
| 공간 최적화 | O(n) | O(1) | ~1ms |
3.2 0/1 배낭 문제 (Knapsack)
문제: n개 물건, 각 무게 w[i], 가치 v[i], 배낭 용량 W. 가치 합을 최대화하라.
점화식: dp[i][w] = max(넣지 않음, 넣음)
- 넣지 않음:
dp[i-1][w] - 넣음 (w >= w[i]):
dp[i-1][w-w[i]] + v[i]
#include <vector>
#include <algorithm>
// 0/1 배낭 - 타뷸레이션
// 시간: O(n×W), 공간: O(n×W)
int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = static_cast<int>(weights.size());
// dp[i][w] = i번째 물건까지 고려, 용량 w에서 최대 가치
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
dp[i][w] = dp[i - 1][w]; // 넣지 않음
if (w >= weights[i - 1]) {
dp[i][w] = std::max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][W];
}공간 최적화 (1차원 배열):
// ✅ O(n×W) 시간, O(W) 공간 - 역순으로 채워 중복 덮어쓰기 방지
int knapsack_optimized(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = static_cast<int>(weights.size());
std::vector<int> dp(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = W; w >= weights[i]; --w) { // 역순!
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}메모이제이션 버전 (재귀 + 캐시, Top-Down):
// 배낭 - 메모이제이션: (i, w) 상태를 캐시
// 장점: 실제로 필요한 (i,w)만 계산. W가 크고 사용되는 상태가 희소할 때 유리
int knapsack_memo(int i, int w, const std::vector<int>& weights,
const std::vector<int>& values,
std::vector<std::vector<int>>& cache) {
if (i == 0 || w <= 0) return 0;
if (cache[i][w] != -1) return cache[i][w];
int skip = knapsack_memo(i - 1, w, weights, values, cache);
int take = (w >= weights[i - 1])
? knapsack_memo(i - 1, w - weights[i - 1], weights, values, cache) + values[i - 1]
: 0;
return cache[i][w] = std::max(skip, take);
}
int knapsack_memo_entry(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = static_cast<int>(weights.size());
std::vector<std::vector<int>> cache(n + 1, std::vector<int>(W + 1, -1));
return knapsack_memo(n, W, weights, values, cache);
}3.3 최장 공통 부분 수열 (LCS)
문제: 두 문자열 s1, s2의 최장 공통 부분 수열 길이. (부분 수열은 연속일 필요 없음)
점화식:
s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1] + 1- else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#include <string>
#include <vector>
#include <algorithm>
// LCS 길이 - 타뷸레이션
// 시간: O(n×m), 공간: O(n×m)
int lcs_length(const std::string& s1, const std::string& s2) {
int n = static_cast<int>(s1.size());
int m = static_cast<int>(s2.size());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}LCS 문자열 복원:
// LCS 문자열 자체를 구하기
std::string lcs_string(const std::string& s1, const std::string& s2) {
int n = static_cast<int>(s1.size());
int m = static_cast<int>(s2.size());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 역추적
std::string result;
int i = n, j = m;
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) {
result.push_back(s1[i - 1]);
--i; --j;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
--i;
} else {
--j;
}
}
std::reverse(result.begin(), result.end());
return result;
}LCS 메모이제이션 버전:
// LCS - 메모이제이션: (i, j) 상태 캐시
int lcs_memo(int i, int j, const std::string& s1, const std::string& s2,
std::vector<std::vector<int>>& cache) {
if (i == 0 || j == 0) return 0;
if (cache[i][j] != -1) return cache[i][j];
if (s1[i - 1] == s2[j - 1]) {
return cache[i][j] = lcs_memo(i - 1, j - 1, s1, s2, cache) + 1;
}
return cache[i][j] = std::max(
lcs_memo(i - 1, j, s1, s2, cache),
lcs_memo(i, j - 1, s1, s2, cache)
);
}
int lcs_length_memo(const std::string& s1, const std::string& s2) {
int n = static_cast<int>(s1.size()), m = static_cast<int>(s2.size());
std::vector<std::vector<int>> cache(n + 1, std::vector<int>(m + 1, -1));
return lcs_memo(n, m, s1, s2, cache);
}3.4 최장 증가 부분 수열 (LIS)
문제: 수열에서 가장 긴 증가하는 부분 수열의 길이. (원소 순서 유지, 연속일 필요 없음)
DP O(n²) 방법:
#include <vector>
#include <algorithm>
// LIS - dp[i] = nums[i]를 끝으로 하는 LIS 길이
// 시간: O(n²), 공간: O(n)
int lis_dp(const std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
if (n == 0) return 0;
std::vector<int> dp(n, 1); // 최소 1 (자기 자신)
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
}
return *std::max_element(dp.begin(), dp.end());
}이진 탐색 O(n log n) 방법:
// LIS - 이진 탐색으로 tail 배열 유지
// tail[i] = 길이 (i+1)인 증가 수열의 마지막 원소 최소값
// 시간: O(n log n), 공간: O(n)
int lis_binary(const std::vector<int>& nums) {
std::vector<int> tail;
for (int x : nums) {
auto it = std::lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x);
} else {
*it = x;
}
}
return static_cast<int>(tail.size());
}| 방법 | 시간 | 공간 | 비고 |
|---|---|---|---|
| DP | O(n²) | O(n) | LIS 길이만 구할 때 |
| 이진 탐색 | O(n log n) | O(n) | n이 클 때 권장 |
3.5 편집 거리 (Levenshtein Distance)
문제: 두 문자열 s1, s2를 같게 만들기 위한 최소 편집 횟수. (삽입, 삭제, 치환 각 1회)
점화식:
s1[i-1]==s2[j-1]:dp[i][j] = dp[i-1][j-1](변경 불필요)- else:
dp[i][j] = 1 + min(삽입, 삭제, 치환)- 삽입:
dp[i][j-1]— s2[j-1]를 s1에 삽입 - 삭제:
dp[i-1][j]— s1[i-1] 삭제 - 치환:
dp[i-1][j-1]— s1[i-1]을 s2[j-1]로 치환
- 삽입:
타뷸레이션:
// 편집 거리 - 타뷸레이션
// 시간: O(n×m), 공간: O(n×m)
int edit_distance(const std::string& s1, const std::string& s2) {
int n = static_cast<int>(s1.size()), m = static_cast<int>(s2.size());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 0; i <= n; ++i) dp[i][0] = i; // s1을 빈 문자열로 만들기
for (int j = 0; j <= m; ++j) dp[0][j] = j; // 빈 문자열을 s2로 만들기
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + std::min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]});
}
}
return dp[n][m];
}편집 거리 메모이제이션 버전:
// 편집 거리 - 메모이제이션
int edit_distance_memo(int i, int j, const std::string& s1, const std::string& s2,
std::vector<std::vector<int>>& cache) {
if (i == 0) return j;
if (j == 0) return i;
if (cache[i][j] != -1) return cache[i][j];
if (s1[i - 1] == s2[j - 1]) {
return cache[i][j] = edit_distance_memo(i - 1, j - 1, s1, s2, cache);
}
int insert = edit_distance_memo(i, j - 1, s1, s2, cache);
int del = edit_distance_memo(i - 1, j, s1, s2, cache);
int replace = edit_distance_memo(i - 1, j - 1, s1, s2, cache);
return cache[i][j] = 1 + std::min({insert, del, replace});
}
int edit_distance_memo_entry(const std::string& s1, const std::string& s2) {
int n = static_cast<int>(s1.size()), m = static_cast<int>(s2.size());
std::vector<std::vector<int>> cache(n + 1, std::vector<int>(m + 1, -1));
return edit_distance_memo(n, m, s1, s2, cache);
}편집 거리 공간 최적화 (2행):
// O(n×m) 시간, O(min(n,m)) 공간 — 짧은 문자열 길이만큼만
int edit_distance_optimized(const std::string& s1, const std::string& s2) {
if (s1.size() < s2.size()) return edit_distance_optimized(s2, s1);
int n = static_cast<int>(s1.size()), m = static_cast<int>(s2.size());
std::vector<int> prev(m + 1), curr(m + 1);
for (int j = 0; j <= m; ++j) prev[j] = j;
for (int i = 1; i <= n; ++i) {
curr[0] = i;
for (int j = 1; j <= m; ++j) {
if (s1[i-1] == s2[j-1]) curr[j] = prev[j-1];
else curr[j] = 1 + std::min({curr[j-1], prev[j], prev[j-1]});
}
std::swap(prev, curr);
}
return prev[m];
}3.6 계단 오르기·동전 거스름돈
계단 오르기 (LeetCode 70): n칸을 1칸 또는 2칸씩 올라가는 방법의 수. dp[i]=dp[i-1]+dp[i-2].
int climb_stairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; ++i) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}동전 거스름돈 (LeetCode 322): 금액 amount를 만들 때 최소 동전 수.
int coin_change(int amount, const std::vector<int>& coins) {
const int INF = amount + 1;
std::vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int a = 1; a <= amount; ++a) {
for (int c : coins) {
if (a >= c) dp[a] = std::min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] == INF ? -1 : dp[amount];
}3.7 DP 문제 유형별 선택 가이드
| 유형 | 대표 예제 | 점화식 | 공간 최적화 |
|---|---|---|---|
| 선형 1D | 피보나치, 계단 | dp[i]=f(dp[i-1],dp[i-2]) | O(1) |
| 2D 시퀀스 | LCS, 편집거리 | dp[i][j]=f(dp[i-1][j],dp[i][j-1],...) | 2행 |
| 배낭 | 0/1 배낭 | dp[i][w]=max(넣지않음, 넣음) | 1행 역순 |
| 구간 DP | 행렬 곱셈 | dp[i][j]=구간[i,j] 최적해 | 2D |
| 상태 압축 | TSP | dp[mask][i] | 비트 연산 |
4. 자주 발생하는 에러와 해결법
에러 1: 스택 오버플로우 (재귀 깊이 초과)
증상: fib(100000) 메모이제이션에서 Segmentation fault 또는 스택 오버플로우.
원인: 재귀 호출이 깊어져 스택 한계를 초과합니다. (일반적으로 수천~수만 단계)
해결: 타뷸레이션으로 전환. 반복문은 스택을 사용하지 않습니다.
// ❌ n이 크면 스택 오버플로우
long long fib_memo(int n, std::vector<long long>& cache) {
if (n <= 1) return n;
if (cache[n] != -1) return cache[n];
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
return cache[n];
}
// ✅ 타뷸레이션 - 스택 무관
long long fib_tab(int n) {
if (n <= 1) return n;
std::vector<long long> dp(n + 1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}에러 2: 배낭 문제에서 공간 최적화 시 잘못된 순서
증상: 1차원 배열로 배낭을 구현했는데 결과가 잘못 나옵니다.
원인: w를 오름차순으로 채우면, 같은 물건을 여러 번 넣는 것처럼 계산됩니다 (완전 배낭이 됨). 0/1 배낭은 내림차순이어야 합니다.
// ❌ 오름차순 - 같은 물건 중복 사용
for (int w = weights[i]; w <= W; ++w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}
// ✅ 내림차순 - 각 물건 1회만
for (int w = W; w >= weights[i]; --w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}에러 3: 초기값/경계 처리 누락
증상: dp[0]을 설정하지 않아 잘못된 결과가 나옵니다.
원인: DP는 이전 상태에 의존합니다. dp[0] 등 경계값을 명시적으로 설정해야 합니다.
// ❌ dp[0] 미설정 - 쓰레기값 사용
std::vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i-1] + ...; // dp[0]이 초기화 안 됨
}
// ✅ 경계값 명시
dp[0] = 0; // 또는 문제에 맞는 초기값
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = ...;
}에러 4: 오버플로우 (피보나치 등)
증상: fib(90) 이상에서 음수 또는 잘못된 값이 나옵니다.
원인: int는 약 21억까지. fib(47)만 해도 32비트 int를 초과합니다.
해결: long long 또는 uint64_t 사용. 더 큰 수는 __int128 또는 BigInt 라이브러리.
// ❌ int - fib(47)에서 오버플로우
int fib(int n) { ... }
// ✅ long long - fib(92) 정도까지
long long fib(int n) { ... }에러 5: LIS에서 이진 탐색 비교자 오류
증상: std::lower_bound 사용 시 LIS 길이가 잘못 나옵니다.
원인: lower_bound는 “이상”을 찾습니다. LIS는 strictly 증가이므로 lower_bound가 맞습니다. 단, “이상 증가”를 구할 때는 upper_bound를 써야 할 수 있습니다.
// LIS: strictly 증가 (같은 값 불가) → lower_bound
auto it = std::lower_bound(tail.begin(), tail.end(), x);
// 비감소 LIS (같은 값 허용) → upper_bound
auto it = std::upper_bound(tail.begin(), tail.end(), x);에러 6: 인덱스 0과 1 기반 혼동
증상: dp[i]와 nums[i-1]을 혼동해 인덱스 에러 또는 잘못된 결과.
원인: DP 테이블은 보통 1-based (길이 n일 때 1..n), 입력 배열은 0-based (0..n-1)입니다.
해결: 주석으로 명확히 표기하고, weights[i-1]처럼 -1 보정을 일관되게 적용합니다.
// dp[i] = "i번째 물건까지" (1-based)
// weights[i-1] = 실제 i번째 물건의 무게 (0-based 배열)
for (int i = 1; i <= n; ++i) {
if (w >= weights[i - 1]) { // i-1 주의
dp[i][w] = std::max(...);
}
}에러 7: 메모이제이션에서 캐시 초기값
증상: cache를 0으로 초기화했는데, 결과가 0인 경우와 “아직 계산 안 함”을 구분하지 못합니다.
원인: 피보나치에서 fib(0)=0이므로, cache[0]=0이 “계산됨”인지 “초기값”인지 모호합니다.
해결: 계산 불가능한 값(-1, -2, std::nullopt)으로 초기화합니다.
// ❌ 0으로 초기화 - fib(0)=0과 구분 불가
std::vector<long long> cache(n + 1, 0);
// ✅ -1로 초기화 (또는 std::optional)
std::vector<long long> cache(n + 1, -1);
if (cache[n] != -1) return cache[n];에러 8: 완전 배낭 vs 0/1 배낭 혼동
증상: “각 물건을 무제한으로 쓸 수 있다”는 완전 배낭인데 0/1 배낭 코드를 써서 잘못된 결과.
원인: 0/1 배낭은 역순(w 내림차순), 완전 배낭은 순방향(w 오름차순)으로 채워야 합니다.
// 0/1 배낭: 각 물건 1회 — 역순
for (int w = W; w >= weights[i]; --w) { ... }
// 완전 배낭: 각 물건 무제한 — 순방향
for (int w = weights[i]; w <= W; ++w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}5. 베스트 프랙티스
5.1 점화식 우선, 구현 나중
원칙: 코드를 작성하기 전에 점화식을 종이에 적고 초기값·경계를 명확히 합니다.
예: 배낭 문제
dp[i][w] = "i번째 물건까지 고려, 용량 w에서 최대 가치"
dp[0][*] = 0 (물건 없음)
dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) if w >= w_i5.2 메모이제이션 vs 타뷸레이션 선택 가이드
| 상황 | 권장 | 이유 |
|---|---|---|
| n이 작음 (< 1000) | 둘 다 가능 | 취향에 따라 |
| n이 큼 (> 10000) | 타뷸레이션 | 스택 오버플로우 방지 |
| 필요한 상태가 희소 | 메모이제이션 | 불필요한 계산 생략 |
| 캐시 지역성 중요 | 타뷸레이션 | 순차 접근에 유리 |
| 디버깅 용이성 | 타뷸레이션 | 테이블 전체를 출력해 검증 |
5.3 명명 규칙
// dp[i] = "i번째까지" 또는 "길이 i인 경우"의 최적값
// cache[i][j] = 메모이제이션용 (i, j) 상태 결과
// dp[i][w] = 배낭: i번째 물건, 용량 w
// dp[i][j] = LCS/편집거리: s1[0..i], s2[0..j]5.4 경계값 테스트
DP는 n=0, n=1, 빈 입력에서 자주 실패합니다. 반드시 테스트합니다.
// 피보나치: fib(0)=0, fib(1)=1
assert(fib(0) == 0 && fib(1) == 1);
// LCS: 빈 문자열 vs 빈 문자열 = 0
assert(lcs_length("", "") == 0);
// 배낭: 용량 0이면 0
assert(knapsack(0, weights, values) == 0);5.5 시간·공간 복잡도 분석 습관
구현 후 반드시 복잡도를 명시합니다:
// 시간: O(n×W), 공간: O(n×W)
int knapsack(...);
// 시간: O(n×m), 공간: O(min(n,m)) — 2행 슬라이딩
int edit_distance_optimized(...);6. 최적화 패턴
6.1 공간 최적화: 슬라이딩 윈도우
이전 상태가 일부 행/열만 필요할 때, 전체 테이블 대신 1~2개 행만 유지합니다.
// 2행만 유지 - dp[i]와 dp[i-1]만 필요
int knapsack_2rows(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = static_cast<int>(weights.size());
std::vector<int> prev(W + 1, 0), curr(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = 0; w <= W; ++w) {
curr[w] = prev[w];
if (w >= weights[i]) {
curr[w] = std::max(curr[w], prev[w - weights[i]] + values[i]);
}
}
std::swap(prev, curr);
}
return prev[W];
}6.2 상태 압축 (비트마스크)
상태가 작은 정수 집합일 때, 비트로 표현해 cache 키를 단순화합니다.
// 여행하는 외판원 문제(TSP) - 방문 집합을 비트로
// dp[mask][i] = mask에 있는 도시만 방문하고 i에 있을 때 최소 비용
int tsp(const std::vector<std::vector<int>>& dist) {
int n = static_cast<int>(dist.size());
int full = (1 << n) - 1;
std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, -1));
auto solve = [&](auto& self, int mask, int pos) -> int {
if (mask == full) return dist[pos][0];
if (dp[mask][pos] != -1) return dp[mask][pos];
int res = INT_MAX;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i))) {
res = std::min(res, dist[pos][i] + self(self, mask | (1 << i), i));
}
}
return dp[mask][pos] = res;
};
return solve(solve, 1, 0);
}5.3 메모이제이션 캐시 선택
| 상황 | 권장 | 이유 |
|---|---|---|
| 인덱스가 연속 정수 | std::vector | O(1) 접근, 캐시 친화적 |
| 인덱스가 희소/복합 키 | std::unordered_map | 유연함 |
| C++17+ | std::optional 또는 -1 | 값 없음 표현 |
// vector - 인덱스가 0..n
std::vector<long long> cache(n + 1, -1);
// unordered_map - 복합 키 (i, j)
std::unordered_map<int64_t, int> cache;
auto key = { return (int64_t)i << 32 | j; };6.4 DP vs 그리디 vs 분할정복
| 구분 | DP | 그리디 | 분할정복 |
|---|---|---|---|
| 중복 부분 문제 | 있음 | 없음 | 없음 (또는 무시) |
| 최적 부분 구조 | 있음 | 있음 | 있음 |
| 선택 | 모든 후보 탐색 후 최적 | 매 단계 국소 최적 | 분할 후 재귀 |
| 예시 | 배낭, LCS | 동전 거스름돈, MST | 병합 정렬, 퀵소트 |
그리디가 안 되는 경우: 배낭 문제에서 “단위 무게당 가치”로 그리디하면 최적이 아닐 수 있습니다. 반례: W=50, (20, 60), (30, 50), (10, 10) → 그리디는 (20,60)+(30,50) 불가, (20,60)+(10,10)=70이지만 최적은 (30,50)+(10,10)+… 등.
분할정복이 적합한 경우: 병합 정렬처럼 부분 문제가 겹치지 않으면 DP가 아닌 분할정복입니다.
6.5 시간 복잡도 줄이기: 슬라이딩 최적화
몇몇 구간 DP에서는 dp[i][j]가 dp[i][k]와 dp[k+1][j]의 조합일 때, 단순 O(n³) 대신 Knuth 최적화 등으로 O(n²)까지 줄일 수 있습니다. (행렬 곱셈 순서 문제 등)
// 행렬 곱셈 순서 - 기본 O(n³) 구간 DP
// dp[i][j] = [i..j] 구간 행렬 곱셈 최소 비용
int matrix_chain(const std::vector<std::pair<int,int>>& dims) {
int n = static_cast<int>(dims.size());
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k) {
int cost = dp[i][k] + dp[k+1][j]
+ dims[i].first * dims[k].second * dims[j].second;
dp[i][j] = std::min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}6. 프로덕션 패턴
6.1 DP 결과 캐싱 (반복 호출 시)
한 번 계산한 DP 결과를 모듈/서비스 수준에서 캐시해 재사용합니다.
#include <mutex>
#include <unordered_map>
class FibCache {
public:
long long get(int n) {
std::lock_guard<std::mutex> lock(mutex_);
auto it = cache_.find(n);
if (it != cache_.end()) return it->second;
long long result = compute(n);
cache_[n] = result;
return result;
}
private:
std::mutex mutex_;
std::unordered_map<int, long long> cache_;
long long compute(int n) {
if (n <= 1) return n;
return get(n - 1) + get(n - 2); // 캐시 통해 재귀
}
};7.2 테스트 케이스로 검증
DP는 경계 조건에서 실수하기 쉽습니다. 테스트 케이스를 반드시 작성합니다.
#include <cassert>
void test_fib() {
assert(fib(0) == 0);
assert(fib(1) == 1);
assert(fib(2) == 1);
assert(fib(10) == 55);
assert(fib(40) == 102334155);
}
void test_knapsack() {
std::vector<int> w = {2, 3, 4, 5}, v = {3, 4, 5, 6};
assert(knapsack(5, w, v) == 7); // 물건 0,1 선택
}
void test_lcs() {
assert(lcs_length("ABCDGH", "AEDFHR") == 3); // "ADH"
assert(lcs_length("ABCD", "ACBD") == 3);
}7.3 로깅과 디버깅
개발 중에는 DP 테이블을 출력해 점화식이 올바른지 확인합니다.
void debug_dp_table(const std::vector<std::vector<int>>& dp) {
for (size_t i = 0; i < dp.size(); ++i) {
for (size_t j = 0; j < dp[i].size(); ++j) {
std::cerr << dp[i][j] << " ";
}
std::cerr << "\n";
}
}
// 사용 예
int result = lcs_length(s1, s2);
#ifdef DEBUG_DP
debug_dp_table(dp);
#endif6.4 실무 활용 사례
| 도메인 | DP 활용 |
|---|---|
| 경로 최적화 | 최단 경로, 경로 개수 |
| 자원 할당 | 배낭, 스케줄링 |
| 시퀀스 비교 | LCS, 편집 거리, DNA 정렬 |
| 금융 | 주가 LIS, 포트폴리오 최적화 |
| NLP | 문장 유사도, 정렬 |
7.5 성능 벤치마크 (참고)
일반적인 PC에서의 대략적인 실행 시간 (n=1000 기준):
| 알고리즘 | 시간 복잡도 | 예상 시간 |
|---|---|---|
| 피보나치 DP | O(n) | < 1ms |
| 배낭 (n=100, W=10000) | O(n×W) | ~100ms |
| LCS (n=m=1000) | O(n×m) | ~10ms |
| LIS DP | O(n²) | ~10ms |
| LIS 이진탐색 | O(n log n) | < 1ms |
| 편집 거리 (n=m=1000) | O(n×m) | ~10ms |
주의: W가 매우 크면 배낭 DP는 비현실적입니다. W가 10^9 수준이면 다른 접근(그리디 근사, 분기 한정)을 고려해야 합니다.
6.6 코딩 테스트에서 DP 문제 식별
다음 키워드가 보이면 DP를 의심합니다.
- “최대/최소”, “최적”, “최소 비용”
- “경로의 개수”, “방법의 수”
- “부분 수열”, “부분 문자열”
- “선택/선택 안 함” (배낭류)
- “이전 상태에 의존”
LeetCode 대표 문제: 70(계단), 72(편집거리), 1143(LCS), 300(LIS), 322(동전), 416(부분합), 518(동전2), 1143(LCS), 300(LIS), 494(타겟합).
8. 구현 체크리스트
DP 문제를 풀 때 다음을 확인하세요.
- 최적 부분 구조가 있는가? (큰 문제 = 작은 문제들의 조합)
- 중복 부분 문제가 있는가? (같은 부분이 반복 등장)
- 점화식을 명확히 세웠는가?
- 초기값/경계를 올바르게 설정했는가?
- 인덱스 범위가 배열 경계를 넘지 않는가?
- 오버플로우 가능성이 있으면
long long등 사용했는가? - 공간 최적화가 가능한가? (이전 상태만 필요할 때)
- 테스트 케이스로 경계값을 검증했는가?
정리
| 항목 | 설명 |
|---|---|
| 메모이제이션 | Top-Down, 재귀 + 캐시, 직관적 |
| 타뷸레이션 | Bottom-Up, 반복 + 테이블, 스택 안전 |
| 공간 최적화 | 슬라이딩 윈도우, 1차원 압축 |
| 실수 방지 | 경계 처리, 순서(배낭), 오버플로우 |
핵심 원칙:
- 점화식을 먼저 세우고 구현한다.
- n이 크면 타뷸레이션을 우선한다.
- 공간 최적화는 점화식 분석 후 적용한다.
- 테스트 케이스로 검증한다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 최적화 문제, 경로 탐색, 자원 할당, 코딩 테스트 등에 활용합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
한 줄 요약: 메모이제이션·타뷸레이션·최적화를 마스터할 수 있습니다.
참고 자료
- cppreference - algorithm
- LeetCode - Dynamic Programming
- 《알고리즘 설계》 - Kleinberg, Tardos
- 《Introduction to Algorithms》 (CLRS) - 15장 동적 계획법
관련 글
- C++ 그래프 알고리즘 완벽 가이드 | BFS·DFS·다익스트라·최소신장트리 [실전]
- C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어·Strassen [실전]
- C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
- C++ 알고리즘 |