pkglog
EN

탐욕 알고리즘이 맞는지 증명하기: 교환 논증과 활동 선택·거스름돈·작업 스케줄링 예제

작성 · · 26분 읽기 · 수정 고급 실습

탐욕 알고리즘은 매 단계에서 지금 가장 좋아 보이는 선택 하나를 고르고, 그 선택을 되돌리지 않습니다. 구현은 대개 “정렬 한 번 + 선형 스캔”으로 짧고 빠르지만, 이 방식이 전체 최적해를 준다는 보장은 문제마다 따로 증명해야 합니다. 회의를 최대한 많이 배정하는 문제에서 “가장 빨리 끝나는 회의부터” 고르는 탐욕은 최적이지만, “가장 먼저 시작하는 회의부터”나 “가장 짧은 회의부터”는 최적이 아닙니다. 코드 모양은 거의 같고 정렬 기준 한 줄만 다른데 결과의 정당성이 갈립니다.

이 글은 탐욕이 통하는 대표 문제들을 C++로 구현하고, 그 탐욕이 왜 맞는지 교환 논증으로 확인하는 방법, 그리고 탐욕이 틀리는 전형적인 경우를 다룹니다.

탐욕이 통하는 문제와 기준

문제탐욕 기준비고
활동 선택 (최대 개수)종료 시간 오름차순시작 시간·길이 기준은 틀림
분수 배낭단위 무게당 가치 내림차순0-1 배낭에는 적용 불가
거스름돈큰 동전부터canonical 동전 체계에서만
최대 지연 최소화마감 시간 오름차순지연의 합 최소화는 다른 문제
최소 회의실 수이벤트를 시간순으로 스캔동시에 열린 최대 개수
허프만 코딩빈도가 가장 낮은 두 노드부터 합침문자 단위 접두 부호 중 최적
최소 신장 트리가벼운 간선부터 (Kruskal)사이클 검사에 Union-Find

탐욕과 동적 계획법 모두 최적 부분 구조, 즉 큰 문제의 최적해가 부분 문제의 최적해로 이루어진다는 성질이 필요합니다. 차이는 선택 방식입니다. DP는 여러 후보 선택의 결과를 모두 계산해 비교하고, 탐욕은 한 가지 선택만 하고 남은 부분 문제 하나로 넘어갑니다. 탐욕이 맞으려면 여기에 더해 “탐욕 선택 속성”, 즉 지금의 국소 최선 선택을 포함하는 전역 최적해가 존재한다는 성질이 성립해야 합니다.

활동 선택

n개의 활동 [시작, 종료)가 있을 때 겹치지 않게 최대 몇 개를 고를 수 있는지 구합니다. 종료 시간이 빠른 순으로 정렬한 뒤, 직전에 고른 활동과 겹치지 않으면 선택합니다.

#include <vector>
#include <algorithm>
#include <limits>

struct Activity {
    int start, finish;
};

std::vector<Activity> maxActivities(std::vector<Activity> activities) {
    std::sort(activities.begin(), activities.end(),
              [](const Activity& a, const Activity& b) { return a.finish < b.finish; });
    std::vector<Activity> result;
    int lastFinish = std::numeric_limits<int>::min();
    for (const auto& act : activities) {
        if (act.start >= lastFinish) {  // 끝나는 시각에 시작하는 활동은 겹치지 않는 것으로 봄
            result.push_back(act);
            lastFinish = act.finish;
        }
    }
    return result;
}

// {1,4}, {3,5}, {0,6}, {5,7}, {3,9}, {5,9}, {6,10}, {8,11}, {8,12}, {2,14}, {12,16}
// → {1,4}, {5,7}, {8,11}, {12,16} 4개

다른 기준이 왜 틀리는지는 반례 하나로 확인됩니다. 시작 시간 기준이라면 [1,10], [2,3], [4,5]에서 [1,10]을 먼저 골라 1개만 얻지만 최적은 2개입니다. 길이 기준이라면 [1,5], [4,7], [6,10]에서 가장 짧은 [4,7]을 먼저 고르면 나머지 둘과 모두 겹쳐 1개만 얻지만, [1,5]와 [6,10]을 고르면 2개입니다.

왜 종료 시간 기준이 맞는가

교환 논증으로 보입니다. 종료 시간이 가장 빠른 활동을 a라 하고, 어떤 최적해 O가 a를 포함하지 않는다고 합시다. O의 활동들 중 가장 먼저 끝나는 것을 b라 하면, a의 종료 시간은 b 이하입니다. O에서 b를 빼고 a를 넣으면, a는 b보다 늦게 끝나지 않으므로 O의 나머지 활동(모두 b가 끝난 뒤에 시작)과 겹치지 않습니다. 활동 수는 그대로이므로 이것도 최적해입니다. 따라서 a를 포함하는 최적해가 항상 존재합니다.

a를 고른 뒤 남는 문제는 “a가 끝난 뒤 시작하는 활동들 중 최대 선택”이라는 같은 형태의 더 작은 문제이고, 여기에 같은 논리를 반복 적용하면 귀납적으로 탐욕 해 전체가 최적임이 따라옵니다. 저는 새 탐욕 전략을 떠올리면 먼저 이렇게 “최적해의 첫 선택을 탐욕 선택으로 바꿔도 해가 나빠지지 않는가”를 따져 보고, 막히는 지점이 있으면 그 지점에서 반례를 찾습니다. 증명이 막히는 곳이 대개 반례가 숨어 있는 곳입니다.

분수 배낭

물건을 일부만 넣을 수 있을 때는 단위 무게당 가치가 높은 순으로 넣고, 마지막 물건은 남은 용량만큼만 넣습니다.

struct Item {
    int value, weight;
};

double fractionalKnapsack(std::vector<Item> items, int capacity) {
    // a.value / a.weight > b.value / b.weight 를 곱셈으로 비교 (부동소수점 오차 회피)
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return 1LL * a.value * b.weight > 1LL * b.value * a.weight;
    });
    double total = 0.0;
    for (const auto& item : items) {
        if (capacity <= 0) break;
        int take = std::min(item.weight, capacity);
        total += static_cast<double>(item.value) * take / item.weight;
        capacity -= take;
    }
    return total;
}
// {60,10}, {100,20}, {120,30}, 용량 50 → 60 + 100 + 120 × 20/30 = 240

교환 논증은 이렇습니다. 최적해가 단위 가치가 낮은 물건을 일부 넣고, 단위 가치가 더 높은 물건을 다 채우지 않았다면, 낮은 쪽을 같은 무게만큼 덜어 높은 쪽으로 바꾸면 총 가치가 늘거나 같습니다. 이 교환을 반복하면 탐욕 해가 됩니다.

같은 논리가 0-1 배낭에서 무너지는 이유는 “같은 무게만큼 덜어 낸다”는 교환이 불가능하기 때문입니다. 위 예를 0-1 배낭으로 풀면 탐욕은 60+100=160에서 멈추고(남은 20에 무게 30은 들어가지 않음), 최적해는 100+120=220입니다. 0-1 배낭은 동적 계획법으로 풉니다.

거스름돈

// 큰 동전부터 사용. canonical 동전 체계에서만 최적
int coinChangeGreedy(std::vector<int> coins, int amount) {
    std::sort(coins.rbegin(), coins.rend());
    int count = 0;
    for (int c : coins) {
        count += amount / c;
        amount %= c;
    }
    return amount == 0 ? count : -1;
}
// {500, 100, 50, 10}, 800 → 500 + 100×3 = 4개

한국 원화나 미국 달러처럼 탐욕이 항상 최적인 동전 체계를 canonical이라고 합니다. 흔한 오해는 “모든 동전이 더 작은 동전의 배수이면 canonical이고 아니면 아니다”라는 것입니다. 배수 관계이면 canonical인 것은 맞지만 그 역은 성립하지 않습니다. 미국 동전 {1, 5, 10, 25}에서 25는 10의 배수가 아니지만 탐욕이 항상 최적입니다. 반대로 {1, 3, 4}는 6에서 탐욕이 4+1+1(3개)을, 최적해가 3+3(2개)을 냅니다.

동전 체계가 고정되어 있다면 확인하는 방법이 있습니다. Kozen과 Zaks의 결과에 따르면, 탐욕이 실패하는 금액이 존재한다면 가장 작은 반례는 가장 큰 두 동전의 합보다 작습니다. 그러므로 그 범위까지 DP 결과와 탐욕 결과를 비교하면 됩니다.

// 동전은 1을 포함한다고 가정
bool isCanonical(std::vector<int> coins) {
    std::sort(coins.begin(), coins.end());
    int n = static_cast<int>(coins.size());
    if (n < 3) return true;  // {1}, {1, c}는 항상 canonical
    int limit = coins[n - 1] + coins[n - 2];
    std::vector<int> dp(limit, 0);  // dp[x] = x를 만드는 최소 동전 수
    for (int x = 1; x < limit; ++x) {
        dp[x] = x;  // 1원짜리로만 만드는 경우
        for (int c : coins)
            if (c <= x) dp[x] = std::min(dp[x], dp[x - c] + 1);
        if (coinChangeGreedy(coins, x) != dp[x]) return false;
    }
    return true;
}
// isCanonical({1, 5, 10, 25}) == true, isCanonical({1, 3, 4}) == false

동전 체계가 입력으로 주어지는 문제라면 이런 확인 대신 처음부터 DP(O(금액 × 동전 수))로 푸는 편이 안전합니다.

최대 지연 최소화

작업마다 처리 시간과 마감 시각이 있고 한 번에 하나씩 처리할 때, 가장 많이 늦은 작업의 지연(완료 시각 − 마감, 음수면 0)을 최소화합니다. 마감이 빠른 순(Earliest Deadline First)으로 처리하면 최적입니다.

struct Job {
    int id, duration, deadline;
};

int minMaxLateness(std::vector<Job> jobs) {
    std::sort(jobs.begin(), jobs.end(),
              [](const Job& a, const Job& b) { return a.deadline < b.deadline; });
    int time = 0, maxLateness = 0;
    for (const auto& j : jobs) {
        time += j.duration;
        maxLateness = std::max(maxLateness, time - j.deadline);
    }
    return maxLateness;
}

교환 논증은 인접한 두 작업에 대해 합니다. 어떤 스케줄에서 마감이 늦은 작업 i가 마감이 빠른 작업 j 바로 앞에 있다면(역전), 둘의 순서를 바꿔도 두 작업이 함께 끝나는 시각은 같고, 바꾼 뒤 i의 지연은 바꾸기 전 j의 지연 이하가 됩니다. 따라서 최대 지연은 늘지 않고, 역전을 모두 없애면 마감 순 스케줄이 됩니다.

주의할 점은 목표 함수입니다. 같은 마감 순 정렬이 “지연의 합” 최소화에는 최적이 아닙니다. 가중치 없는 지연 합(총 tardiness) 최소화는 NP-난해로 알려져 있어 단순한 정렬 기준으로 풀리지 않습니다. 반대로 “완료 시각의 합”을 최소화하는 문제는 처리 시간이 짧은 순(SPT)이 최적입니다. 비슷해 보이는 목표라도 최적인 탐욕 기준이 다르므로, 무엇을 최소화하는지부터 정확히 적어야 합니다.

최소 회의실 수

모든 회의를 수용하는 데 필요한 최소 회의실 수는, 어느 순간에 동시에 진행 중인 회의 수의 최댓값과 같습니다.

int minMeetingRooms(const std::vector<std::pair<int, int>>& meetings) {
    std::vector<std::pair<int, int>> events;  // (시각, +1 시작 / -1 종료)
    for (const auto& [s, e] : meetings) {
        events.push_back({s, 1});
        events.push_back({e, -1});
    }
    // 같은 시각이면 -1(종료)이 +1(시작)보다 먼저 오도록: pair의 기본 비교로 충분
    std::sort(events.begin(), events.end());
    int rooms = 0, maxRooms = 0;
    for (const auto& [t, delta] : events) {
        rooms += delta;
        maxRooms = std::max(maxRooms, rooms);
    }
    return maxRooms;
}

같은 시각에 끝나는 회의와 시작하는 회의가 있을 때 종료를 먼저 처리하므로, [1,3]과 [3,5]는 회의실 하나로 충분하다고 계산됩니다. 문제 조건이 끝나는 시각에 바로 시작할 수 없다면 시작을 먼저 처리하도록 비교 순서를 바꿔야 합니다. 이런 경계 조건은 문제마다 달라서 가장 자주 틀리는 부분입니다.

허프만 코딩

문자 빈도가 주어졌을 때, 빈도가 가장 낮은 두 노드를 반복해서 합쳐 이진 트리를 만들고, 루트에서 잎까지의 경로(왼쪽 0, 오른쪽 1)를 코드로 씁니다.

#include <queue>
#include <memory>
#include <string>
#include <unordered_map>

struct Node {
    char ch;
    long long freq;
    Node* left = nullptr;
    Node* right = nullptr;
};

void buildCodes(const Node* node, const std::string& code,
                std::unordered_map<char, std::string>& codes) {
    if (!node->left && !node->right) {
        codes[node->ch] = code.empty() ? "0" : code;  // 문자가 하나뿐인 경우
        return;
    }
    buildCodes(node->left, code + "0", codes);
    buildCodes(node->right, code + "1", codes);
}

std::unordered_map<char, std::string> huffmanCodes(
        const std::unordered_map<char, long long>& freq) {
    std::unordered_map<char, std::string> codes;
    if (freq.empty()) return codes;

    std::vector<std::unique_ptr<Node>> pool;  // 노드 소유권을 한곳에서 관리
    auto cmp = [](const Node* a, const Node* b) { return a->freq > b->freq; };
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);

    for (const auto& [c, f] : freq) {
        pool.push_back(std::make_unique<Node>(Node{c, f}));
        pq.push(pool.back().get());
    }
    while (pq.size() > 1) {
        Node* l = pq.top(); pq.pop();
        Node* r = pq.top(); pq.pop();
        pool.push_back(std::make_unique<Node>(Node{0, l->freq + r->freq, l, r}));
        pq.push(pool.back().get());
    }
    buildCodes(pq.top(), "", codes);
    return codes;  // pool이 소멸하며 모든 노드 해제
}

노드를 new로 만들고 해제를 빠뜨리는 코드가 흔한데, 위처럼 unique_ptr 벡터에 소유권을 모으면 트리 순회로 지울 필요가 없습니다. 복잡도는 우선순위 큐 연산 때문에 문자 종류 수 n에 대해 O(n log n)입니다.

허프만 코드는 “문자마다 정수 비트 길이의 접두 부호를 부여하는 방식” 중에서 평균 비트 수가 최소입니다. 여러 문자를 묶어 부호화하거나 산술 부호화처럼 문자당 비트 수가 정수가 아니어도 되는 방식은 이보다 더 압축할 수 있으므로, “최적 압축”이라는 표현은 이 범위 안에서만 맞습니다.

구간 병합과 점프 게임

// 겹치는 구간을 병합
std::vector<std::pair<int, int>> mergeIntervals(std::vector<std::pair<int, int>> intervals) {
    std::sort(intervals.begin(), intervals.end());  // 시작 시각 기준
    std::vector<std::pair<int, int>> result;
    for (const auto& iv : intervals) {
        if (!result.empty() && iv.first <= result.back().second) {
            result.back().second = std::max(result.back().second, iv.second);
        } else {
            result.push_back(iv);
        }
    }
    return result;
}

겹침 판정에 <=를 쓰면 [1,4]와 [4,5]가 하나로 합쳐지고, <를 쓰면 따로 남습니다. 닫힌 구간인지 반열린 구간인지에 따라 맞는 쪽이 다르므로 문제 정의를 먼저 확인합니다. 병합 시 std::max로 끝을 갱신하기 때문에, 시작이 같은 구간끼리의 순서는 결과에 영향을 주지 않습니다.

// 마지막 인덱스에 도달할 수 있는가: 지금까지 도달 가능한 최대 인덱스를 유지
bool canJump(const std::vector<int>& nums) {
    long long reach = 0;
    const long long last = static_cast<long long>(nums.size()) - 1;
    for (long long i = 0; i <= last; ++i) {
        if (i > reach) return false;
        reach = std::max(reach, i + nums[i]);  // long long이라 int 범위를 넘어도 안전
        if (reach >= last) return true;
    }
    return true;
}

// 최소 점프 횟수: 현재 점프로 닿는 구간의 끝에 도달할 때마다 한 번 더 점프
int minJumps(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    int jumps = 0;
    long long curEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; ++i) {
        farthest = std::max(farthest, static_cast<long long>(i) + nums[i]);
        if (i == curEnd) {
            ++jumps;
            curEnd = farthest;
        }
    }
    return jumps;  // 도달 가능하다고 가정 (LeetCode 45 조건)
}

i + nums[i]는 nums[i]가 INT_MAX에 가까우면 int에서 넘칩니다. 결과를 std::min(i + nums[i], n - 1)로 잘라도 덧셈이 먼저 일어나 이미 넘친 뒤이므로, 계산 자체를 더 넓은 타입에서 하거나 nums[i] >= last - i처럼 뺄셈으로 비교해야 합니다.

매트로이드: 탐욕이 통하는 구조

탐욕이 언제 최적인지를 일반적으로 설명하는 수학적 구조가 매트로이드입니다. 원소 집합과 “독립 집합”들의 모임이 (1) 독립 집합의 부분집합도 독립이고, (2) 크기가 다른 두 독립 집합이 있으면 큰 쪽에서 원소 하나를 가져와 작은 쪽에 넣어도 독립을 유지할 수 있다(교환 성질)는 두 조건을 만족하면 매트로이드입니다. 매트로이드에서는 무게가 큰 원소부터 “넣어도 독립이면 넣는” 탐욕이 항상 최대 무게 독립 집합을 줍니다.

대표 예가 그래프의 간선 집합에서 “사이클이 없는 간선 집합”을 독립으로 보는 그래픽 매트로이드이고, Kruskal 알고리즘이 바로 이 탐욕입니다. CLRS는 마감이 있는 단위 시간 작업 스케줄링도 매트로이드로 설명합니다.

모든 탐욕 문제가 매트로이드인 것은 아닙니다. 활동 선택에서 “서로 겹치지 않는 활동 집합”은 교환 성질을 만족하지 않습니다. 예를 들어 {[1,10]}과 {[1,5], [6,10]}은 둘 다 독립이지만, 큰 쪽의 어느 원소를 작은 쪽에 넣어도 [1,10]과 겹칩니다. 그래서 활동 선택의 정당성은 매트로이드 정리가 아니라 앞에서 본 교환 논증으로 따로 보여야 합니다.

구현에서 자주 틀리는 부분

정렬 비교자에 <=를 쓰면 안 됩니다. std::sort는 비교자가 strict weak ordering을 만족한다고 가정하는데, a.finish <= b.finish는 같은 원소끼리 비교할 때 참을 돌려줘 이 조건을 위반합니다. 결과는 미정의 동작이고, 구현에 따라 같은 값이 많은 입력에서 배열 범위를 넘어 읽다가 크래시가 나기도 합니다. 동률을 다른 기준으로 깨고 싶다면 std::tie(a.finish, a.start) < std::tie(b.finish, b.start)처럼 사전식 비교를 씁니다.

탐욕 결과가 제약을 만족하는지 확인하는 검증 함수와, 작은 입력에서 모든 경우를 시도하는 브루트포스와 결과를 비교하는 테스트를 함께 두면 잘못된 정렬 기준을 빨리 잡아낼 수 있습니다. 탐욕의 버그는 대부분 “특정 모양의 입력에서만” 드러나므로, 손으로 만든 예제보다 무작위 소규모 입력이 효과적입니다.

#include <cassert>

bool validateActivities(const std::vector<Activity>& selected) {
    for (size_t i = 1; i < selected.size(); ++i)
        if (selected[i].start < selected[i - 1].finish) return false;
    return true;
}

void test_greedy() {
    auto r = maxActivities({{1, 2}, {2, 3}, {3, 4}});
    assert(r.size() == 3 && validateActivities(r));
    assert(maxActivities({{1, 10}, {2, 3}, {4, 5}}).size() == 2);
    assert(minMeetingRooms({{0, 30}, {5, 10}, {15, 20}}) == 2);
    assert(isCanonical({1, 5, 10, 25}) && !isCanonical({1, 3, 4}));
}

참고 자료

  • LeetCode Greedy
  • 《Algorithm Design》 — Kleinberg, Tardos, 4장 (교환 논증, 최대 지연 최소화)
  • 《Introduction to Algorithms》 (CLRS) — 탐욕 알고리즘과 매트로이드
  • D. Kozen, S. Zaks, “Optimal bounds for the change-making problem”, Theoretical Computer Science, 1994

같이 보면 좋은 글