C++ 동적 계획법: 메모이제이션 vs 타뷸레이션, 2D→1D 공간 최적화, 배낭·LCS·Bitmask DP

재귀로 짠 피보나치 fib(40)은 결과 하나를 얻으려고 함수를 3억 3천만 번 넘게 호출합니다. fib(n)의 호출 횟수가 2·fib(n+1) − 1이기 때문인데, 대부분은 이미 계산한 fib(k)를 처음부터 다시 계산하는 낭비입니다. 한 번 계산한 결과를 저장해 두면 호출이 n번 안팎으로 줄어듭니다. 이것이 동적 계획법(DP)의 핵심입니다.

이 글은 DP를 적용할 수 있는 조건을 먼저 정리하고, 메모이제이션과 타뷸레이션의 차이, 대표 문제(배낭, LCS, LIS, 편집 거리, 동전, Bitmask DP)의 C++ 구현, 그리고 순회 방향·초기값·오버플로처럼 결과를 조용히 틀리게 만드는 실수를 다룹니다. 예제는 C++17 이상을 기준으로 합니다.

---

DP를 쓸 수 있는 조건

DP는 두 가지 성질이 있을 때 적용합니다. 첫째, 최적 부분 구조입니다. 큰 문제의 최적해가 작은 문제들의 최적해로 구성됩니다. 둘째, 중복 부분 문제입니다. 같은 작은 문제가 여러 번 등장합니다. 첫째만 있고 둘째가 없으면(예: 병합 정렬) 분할 정복으로 충분하고, 매 단계의 국소 최선이 전체 최선으로 이어진다는 것을 증명할 수 있다면 그리디가 더 간단합니다.

flowchart TD
    A[최적화/계산 문제] --> B{"작은 문제의 답으로\n큰 문제의 답을 만들 수 있나?"}
    B -->|예| C{"같은 부분 문제가\n여러 번 등장?"}
    B -->|아니오| D[다른 접근 검토]
    C -->|예| E[DP]
    C -->|아니오| F[분할 정복]
    E --> G[상태 정의와 점화식]
    G --> H[초기값과 계산 순서]

전형적인 예를 보면 브루트포스와의 차이가 분명합니다. 0/1 배낭에서 물건마다 넣을지 말지를 모두 따지면 2^n가지이고, n=30이면 이미 10억 가지를 넘습니다. 하지만 “i번째 물건까지 보고 용량 w가 남았을 때의 최대 가치”라는 상태로 묶으면 상태 수가 n × W로 줄어듭니다. 두 문자열의 LCS도 한쪽의 모든 부분 수열을 나열하면 2^n개지만, “앞에서 i글자와 j글자까지 봤을 때의 LCS 길이”로 상태를 정의하면 n × m개입니다.

DP 설계에서 가장 중요한 것은 이 상태 정의입니다. 저는 코드를 쓰기 전에 dp[i][w]가 정확히 무엇을 뜻하는지 한 문장으로 적고, 초기값과 계산 순서를 정한 다음에야 구현을 시작하는 편입니다. 상태의 뜻이 모호하면 초기값과 점화식의 경계가 어긋나서, 작은 예제에서는 맞다가 큰 입력에서 틀리는 코드가 나옵니다.

---

메모이제이션과 타뷸레이션

같은 점화식을 두 가지 방향으로 계산할 수 있습니다.

메모이제이션 (top-down)

재귀 구조를 그대로 두고, 계산한 결과를 캐시에 저장했다가 같은 입력이 오면 캐시에서 돌려줍니다.

#include <vector>

// 시간 O(n), 공간 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];  // 이미 계산됨
    return cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
}

long long fib(int n) {
    std::vector<long long> cache(n + 1, -1);
    return fib_memo(n, cache);
}

캐시를 0으로 초기화하면 안 됩니다. fib(0) = 0이라서 “계산했더니 0”과 “아직 계산 안 함”을 구분할 수 없기 때문입니다. 답으로 나올 수 없는 값(-1)이나 std::optional을 씁니다.

타뷸레이션 (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];
}

// 직전 두 값만 필요하므로 공간 O(1)로 줄일 수 있음
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;
}

두 방식의 차이는 실행 순서와 스택 사용입니다. 메모이제이션은 필요한 상태만 계산하므로 상태 공간이 크지만 실제로 도달하는 상태가 적을 때 유리합니다. 반면 재귀 깊이가 상태 수에 비례할 수 있어서, fib_memo(100000)처럼 깊이가 10만을 넘으면 스택 크기(Windows 기본 1MB, 많은 Linux 환경에서 8MB)와 프레임 크기에 따라 스택 오버플로가 날 수 있습니다. 타뷸레이션은 스택을 쓰지 않고 메모리를 순차적으로 접근하므로 캐시 효율이 좋으며, 테이블 전체를 출력해 점화식을 검증하기도 쉽습니다. 대신 모든 상태를 계산하고, 의존 관계에 맞는 계산 순서를 직접 정해야 합니다.

---

0/1 배낭

n개의 물건에 무게 w[i]와 가치 v[i]가 있고 배낭 용량이 W일 때, 가치 합을 최대화합니다. dp[i][c]를 “앞에서 i개 물건만 고려했을 때 용량 c로 얻을 수 있는 최대 가치”로 정의하면, i번째 물건을 넣지 않는 경우 dp[i-1][c], 넣는 경우(c ≥ w) dp[i-1][c - w] + v 중 큰 값이 답입니다.

#include <vector>
#include <algorithm>

// 시간 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());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int c = 0; c <= W; ++c) {
            dp[i][c] = dp[i - 1][c];                      // 넣지 않음
            if (c >= weights[i - 1]) {                    // 입력 배열은 0-based
                dp[i][c] = std::max(dp[i][c],
                    dp[i - 1][c - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][W];
}

테이블은 “물건 0개”를 나타내는 행이 필요해 1-based로, 입력 배열은 0-based로 쓰는 경우가 많습니다. weights[i - 1]의 - 1을 한 군데라도 빠뜨리면 인덱스가 하나씩 밀리는데, 이 버그는 예제 입력에서 우연히 맞는 답이 나오기도 해서 찾기 어렵습니다.

1차원으로 줄이기

dp[i] 행은 dp[i-1] 행만 참조하므로 한 행으로 줄일 수 있습니다. 이때 용량을 큰 쪽에서 작은 쪽으로 순회해야 합니다.

// 시간 O(n·W), 공간 O(W)
int knapsack_1d(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    std::vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i) {
        for (int c = W; c >= weights[i]; --c) {  // 내림차순
            dp[c] = std::max(dp[c], dp[c - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

dp[c]를 갱신할 때 참조하는 dp[c - weights[i]]는 아직 이번 물건을 반영하기 전의 값, 즉 이전 행의 값이어야 합니다. 큰 c부터 내려가면 더 작은 인덱스는 아직 갱신되지 않았으므로 이 조건이 지켜집니다. 오름차순으로 돌면 방금 이번 물건을 넣어 갱신한 값을 다시 참조하게 되어, 같은 물건을 여러 번 넣는 완전 배낭(unbounded knapsack)의 답이 나옵니다. 거꾸로 문제가 완전 배낭이라면 오름차순이 맞습니다. 이 한 줄의 방향 차이는 컴파일 에러도 런타임 에러도 내지 않고 답만 바꾸므로, 저는 1차원 배낭 코드를 볼 때 루프 방향부터 확인합니다.

1차원으로 줄이면 어떤 물건을 골랐는지 역추적할 수 없게 됩니다. 선택 목록까지 필요하다면 2D 테이블을 유지하거나, 물건별로 선택 여부를 기록하는 비트 테이블을 따로 둡니다.

메모이제이션 버전

int knapsack_memo(int i, int c, const std::vector<int>& weights,
                  const std::vector<int>& values,
                  std::vector<std::vector<int>>& cache) {
    if (i == 0) return 0;
    if (cache[i][c] != -1) return cache[i][c];
    int best = knapsack_memo(i - 1, c, weights, values, cache);
    if (c >= weights[i - 1]) {
        best = std::max(best, knapsack_memo(i - 1, c - weights[i - 1], weights, values, cache)
                              + values[i - 1]);
    }
    return cache[i][c] = best;
}

캐시 크기는 여전히 (n+1) × (W+1)이지만, 실제로 방문하는 (i, c) 조합만 계산합니다. 무게가 모두 큰 값의 배수처럼 도달 가능한 용량이 드문드문하면 계산량이 크게 줄어듭니다.

용량 W가 10^9처럼 크면 O(n·W) 자체가 불가능합니다. 이때 가치 합이 작다면 “가치 v를 얻기 위한 최소 무게”를 상태로 바꾸는 DP로 돌리고, 그것도 크다면 분기 한정이나 근사 알고리즘을 검토합니다.

---

최장 공통 부분 수열 (LCS)

두 문자열에서 순서를 유지한 채 공통으로 뽑을 수 있는 가장 긴 부분 수열의 길이를 구합니다. 부분 수열이므로 연속일 필요는 없습니다. dp[i][j]를 “s1의 앞 i글자와 s2의 앞 j글자의 LCS 길이”로 두면, 마지막 글자가 같을 때 dp[i-1][j-1] + 1, 다를 때 한쪽 글자를 버린 두 경우 중 큰 값입니다.

#include <string>
#include <vector>
#include <algorithm>

// 시간 O(n·m), 공간 O(n·m). LCS 문자열까지 역추적
std::string lcs_string(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 = 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]);
        }
    }
    // (n, m)에서 거꾸로 따라가며 복원
    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_string("ABCDGH", "AEDFHR") == "ADH"

LCS가 여러 개일 때 역추적은 그중 하나만 돌려주며, >=와 > 중 무엇을 쓰느냐에 따라 어느 것이 나오는지가 달라집니다. diff 같은 도구가 같은 입력에 대해 도구마다 다른 결과를 내는 이유 중 하나가 이런 동점 처리입니다. 길이만 필요하다면 편집 거리와 같은 방식으로 두 행만 유지해 공간을 O(min(n, m))으로 줄일 수 있습니다.

---

최장 증가 부분 수열 (LIS)

수열에서 순서를 유지하며 뽑은 엄격히 증가하는 부분 수열 중 가장 긴 것의 길이입니다.

// dp[i] = nums[i]로 끝나는 LIS 길이. 시간 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);
    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());
}

// tail[k] = 길이 k+1인 증가 부분 수열들의 마지막 원소 중 최솟값. 시간 O(n log 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());
}

tail은 항상 정렬된 상태를 유지하므로 이진 탐색을 쓸 수 있습니다. 엄격히 증가하는 수열에서는 같은 값이 들어오면 기존 값을 대체해야 하므로 lower_bound(x 이상인 첫 위치)를 쓰고, 같은 값을 허용하는 비감소 수열이라면 upper_bound(x 초과인 첫 위치)를 씁니다. 이 둘을 바꿔 쓰면 중복 값이 있는 입력에서만 답이 틀려집니다. 또 tail 배열 자체는 실제 LIS가 아니므로, 수열을 복원하려면 각 원소가 들어간 위치와 직전 원소의 인덱스를 따로 기록해야 합니다.

---

편집 거리 (Levenshtein)

s1을 s2로 바꾸는 데 필요한 삽입·삭제·치환의 최소 횟수입니다. dp[i][j]를 “s1의 앞 i글자를 s2의 앞 j글자로 바꾸는 최소 비용”으로 두면, 마지막 글자가 같을 때는 dp[i-1][j-1], 다를 때는 삽입(dp[i][j-1]), 삭제(dp[i-1][j]), 치환(dp[i-1][j-1]) 중 최솟값에 1을 더합니다. 빈 문자열에서 j글자를 만드는 비용은 j, i글자를 빈 문자열로 만드는 비용은 i라는 초기값이 중요합니다.

// 시간 O(n·m), 공간 O(min(n, m)): 두 행만 유지
int edit_distance(const std::string& s1, const std::string& s2) {
    if (s1.size() < s2.size()) return edit_distance(s2, s1);  // s2를 짧은 쪽으로
    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];
}
// edit_distance("kitten", "sitting") == 3

curr[j - 1](같은 행, 왼쪽)과 prev[j - 1](이전 행, 대각선)을 모두 참조하므로 한 행으로 줄이려면 대각선 값을 임시 변수에 보관해야 합니다. 두 행을 쓰는 편이 실수할 여지가 적습니다.

---

동전 거스름돈과 계단 오르기

// 금액 amount를 만드는 최소 동전 수 (각 동전 무제한). 불가능하면 -1
int coin_change(int amount, const std::vector<int>& coins) {
    const int INF = amount + 1;  // 답은 최대 amount개이므로 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];
}

INF를 INT_MAX로 잡으면 dp[a - c] + 1에서 오버플로가 나므로, 답의 상한보다 하나 큰 값을 쓰는 것이 깔끔합니다. 동전 문제는 그리디로 풀리는 것처럼 보이지만, 동전이 {1, 3, 4}이고 금액이 6이면 큰 동전부터 고르는 그리디는 4+1+1(3개)을, 최적해는 3+3(2개)을 냅니다. 한국 원화나 미국 달러처럼 그리디가 성립하는 동전 체계는 특수한 경우입니다.

계단을 1칸 또는 2칸씩 오르는 방법의 수는 dp[i] = dp[i-1] + dp[i-2]로 피보나치와 같은 점화식이며, 같은 방식으로 O(1) 공간에 풀 수 있습니다.

---

Bitmask DP: 외판원 문제

상태가 “어떤 원소들을 이미 골랐는가”라는 집합일 때, 원소가 적다면 집합을 정수의 비트로 표현할 수 있습니다. 외판원 문제(TSP)에서 방문한 도시 집합을 mask로 두면 다음과 같습니다.

#include <vector>
#include <climits>
#include <algorithm>

// dp[mask][pos] = mask의 도시를 방문했고 지금 pos에 있을 때,
//                 남은 도시를 모두 돌고 0으로 돌아가는 최소 비용
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 next = 0; next < n; ++next) {
            if (!(mask & (1 << next))) {
                res = std::min(res, dist[pos][next] + self(self, mask | (1 << next), next));
            }
        }
        return dp[mask][pos] = res;
    };
    return solve(solve, 1, 0);  // 도시 0에서 출발, 0만 방문한 상태
}

상태가 2^n × n개이고 상태마다 n개의 전이가 있으므로 시간은 O(2^n · n²), 공간은 O(2^n · n)입니다. 모든 순열을 시도하는 O(n!)보다 훨씬 작지만 여전히 지수적이어서, n이 20 안팎에서 메모리와 시간 모두 한계에 가까워집니다. 재귀 깊이는 n 이하라 스택 문제는 없습니다.

---

구간 DP: 행렬 곱셈 순서

행렬 A₁…Aₙ을 곱하는 순서에 따라 스칼라 곱셈 횟수가 크게 달라집니다. dp[i][j]를 “Aᵢ…Aⱼ를 곱하는 최소 비용”으로 두고, 마지막으로 나누는 위치 k를 모두 시도합니다.

#include <climits>

// dims[i] = {행, 열}. 시간 O(n³), 공간 O(n²)
long long matrix_chain(const std::vector<std::pair<int, int>>& dims) {
    int n = static_cast<int>(dims.size());
    std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, 0));
    for (int len = 2; len <= n; ++len) {          // 짧은 구간부터
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MAX;
            for (int k = i; k < j; ++k) {
                long long cost = dp[i][k] + dp[k + 1][j]
                    + 1LL * dims[i].first * dims[k].second * dims[j].second;
                dp[i][j] = std::min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

구간 DP는 길이가 짧은 구간부터 채워야 합니다. dp[i][k]와 dp[k+1][j]가 모두 dp[i][j]보다 짧은 구간이기 때문입니다. 일부 구간 DP는 최적 분할점이 단조롭다는 조건(사각 부등식)을 만족할 때 Knuth 최적화로 O(n²)까지 줄일 수 있는데, 최적 이진 탐색 트리가 대표적인 예입니다. 행렬 곱셈 순서 문제는 이 조건을 일반적으로 만족하지 않아 Knuth 최적화를 그대로 적용할 수 없고, 더 빠른 해법(Hu–Shing의 O(n log n) 알고리즘)은 별도의 기법을 씁니다.

---

결과를 조용히 틀리게 만드는 실수

초기값을 잘못 잡음

std::vector<int> dp(n + 1)은 모든 원소를 0으로 초기화하므로 쓰레기 값이 들어가지는 않습니다. 문제는 0이 그 문제에서 맞는 초기값이 아닐 때입니다. 최솟값을 구하는 DP(동전 문제)에서 도달 불가능한 상태를 0으로 두면 모든 답이 0이 되고, 경우의 수를 세는 DP에서 dp[0] = 1(아무것도 고르지 않는 방법 1가지)을 빠뜨리면 모든 답이 0이 됩니다. 스택에 선언한 원시 배열 int dp[100];은 정말로 초기화되지 않으므로 더 위험합니다.

정수 오버플로

fib(47)은 2,971,215,073으로 32비트 int의 최댓값(2,147,483,647)을 넘습니다. long long으로 바꾸면 fib(92)까지 담을 수 있고 fib(93)에서 다시 넘칩니다. 경우의 수를 세는 문제에서 “10^9+7로 나눈 나머지를 출력하라”는 조건이 붙는 이유가 이것이며, 이때는 덧셈마다 나머지를 취하고 곱셈 전에는 long long으로 올려야 합니다. 부호 있는 정수 오버플로는 C++에서 미정의 동작이라, 음수로 바뀌는 것조차 보장되지 않습니다.

경계 입력

DP는 n=0, 빈 문자열, 용량 0 같은 경계에서 자주 틀립니다. 작은 테스트를 몇 개 두면 대부분 잡힙니다.

#include <cassert>

void test_dp() {
    assert(fib(0) == 0 && fib(1) == 1 && fib(10) == 55);
    assert(fib(40) == 102334155);

    std::vector<int> w = {2, 3, 4, 5}, v = {3, 4, 5, 6};
    assert(knapsack(5, w, v) == 7);        // 물건 0, 1 선택
    assert(knapsack(0, w, v) == 0);
    assert(knapsack_1d(5, w, v) == 7);

    assert(lcs_string("ABCDGH", "AEDFHR") == "ADH");
    assert(lcs_string("", "") == "");
    assert(edit_distance("kitten", "sitting") == 3);
    assert(lis_binary({10, 9, 2, 5, 3, 7, 101, 18}) == 4);
    assert(coin_change(6, {1, 3, 4}) == 2);
}

2D 버전과 1D 버전의 결과를 무작위 입력에서 비교하는 테스트도 효과적입니다. 공간 최적화 과정에서 생긴 순회 방향 실수를 거의 확실하게 잡아냅니다.

---

DP, 그리디, 분할 정복

구분	DP	그리디	분할 정복
중복 부분 문제	있음	따지지 않음	없음
선택 방식	모든 후보의 결과를 비교	매 단계 국소 최선 하나만	나눠서 각각 풀고 합침
정당성	점화식이 맞으면 성립	교환 논증 등으로 증명 필요	분할·병합이 맞으면 성립
예	0/1 배낭, LCS, 편집 거리	활동 선택, 최소 신장 트리	병합 정렬, 퀵 정렬

0/1 배낭에 “단위 무게당 가치가 높은 순서” 그리디를 쓰면 틀릴 수 있습니다. 용량 50, 물건이 (무게 10, 가치 60), (20, 100), (30, 120)이라면 단위 가치는 6, 5, 4라서 그리디는 앞의 두 개를 넣어 160을 얻고 세 번째는 들어가지 않습니다. 최적해는 두 번째와 세 번째를 넣은 220입니다. 물건을 쪼갤 수 있는 분할 배낭이라면 같은 그리디가 최적입니다.

LeetCode에서 연습할 만한 문제로는 70(계단 오르기), 322·518(동전), 416(부분집합 합 분할), 494(타깃 합), 300(LIS), 1143(LCS), 72(편집 거리)가 있습니다.

---

참고 자료

• LeetCode - Dynamic Programming
• 《Algorithm Design》 - Kleinberg, Tardos, 6장
• 《Introduction to Algorithms》 (CLRS) - 동적 계획법 장

같이 보면 좋은 글

• C++ 그래프 알고리즘
• C++ 분할정복
• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
• C++ STL 알고리즘 기초: sort·find·transform·accumulate 실전 활용
• 탐욕 알고리즘이 맞는지 증명하기