C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]

들어가며: “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_i

---

5.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);
#endif

---

6.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차원 압축
실수 방지	경계 처리, 순서(배낭), 오버플로우
핵심 원칙:

1. 점화식을 먼저 세우고 구현한다.
2. n이 크면 타뷸레이션을 우선한다.
3. 공간 최적화는 점화식 분석 후 적용한다.
4. 테스트 케이스로 검증한다.

---

자주 묻는 질문 (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++ 알고리즘 |

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

• 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
• 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
• 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
• 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

1. 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
2. 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
3. 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
4. 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
5. 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
• C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·배낭·스케줄링·증명 기법 [실전]
• C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]

---

이 글에서 다루는 키워드 (관련 검색어)

C++, 동적계획법, DP, 알고리즘, 최적화 등으로 검색하시면 이 글이 도움이 됩니다.