C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·배낭·스케줄링·증명 기법 [실전]

Q: 이 내용을 실무에서 언제 쓰나요?

작업 스케줄링, 리소스 할당, 압축(허프만), 캐시 교체(LRU), 최단 경로(다익스트라) 등에 활용합니다.

Q: 선행으로 읽으면 좋은 글은?

정렬, 우선순위 큐, 동적 계획법 기초를 먼저 익히면 탐욕법과의 차이를 이해하기 쉽습니다.

Q: 더 깊이 공부하려면?

LeetCode Greedy 유형, 《알고리즘 설계》 탐욕법 챕터, 매트로이드 이론을 참고하세요.

2026년 4월 7일 · 35분 읽기 · 수정 2026년 4월 7일 고급 실습

이 글의 핵심

C++ 탐욕법(Greedy) 마스터: 활동 선택, 분수 배낭, 거스름돈, 작업 스케줄링, 허프만 코딩. 문제 시나리오, 완전한 예제, 흔한 실수, 증명 기법, 프로덕션 패턴. 탐욕 알고리즘(Greedy)은 매 단계에서 지역적으로 최선의 선택을 해서 전체 최적해를 얻는 기법입니다. 비유하면 "매 순간 가장 비싼 물건을 고르는 것"이 항상 최선은 아니지만, "가장 빨리 끝나는 활동부터 고르는 것"은 최적해를 보장합니다.

들어가며: “최적해를 매 순간 선택하면 되나요?”

실제 겪는 문제 시나리오

탐욕 알고리즘(Greedy)은 매 단계에서 지역적으로 최선의 선택을 해서 전체 최적해를 얻는 기법입니다. 비유하면 “매 순간 가장 비싼 물건을 고르는 것”이 항상 최선은 아니지만, “가장 빨리 끝나는 활동부터 고르는 것”은 최적해를 보장합니다.

flowchart TD
  subgraph wrong[❌ 잘못된 탐욕 선택]
    W1[가장 가치 높은 것부터] --> W2[배낭 문제에서 실패]
    W2 --> W3[최적해 아님]
  end
  subgraph right[✅ 올바른 탐욕 선택]
    R1[종료 시간 빠른 순] --> R2[활동 선택 최적]
    R2 --> R3[최대 활동 수]
  end

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 완전한 탐욕 알고리즘 예제, 자주 하는 실수, 증명 기법, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

탐욕법이 적용되는 문제와 적용되지 않는 문제를 구분할 수 있습니다.
활동 선택, 분수 배낭, 작업 스케줄링 등을 C++로 구현할 수 있습니다.
탐욕 선택의 최적성을 증명하는 기법을 이해할 수 있습니다.

요구 환경: C++17 이상

실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

1. 문제 시나리오

시나리오 1: 회의실 배정 — 겹치는 회의 최대한 많이

상황: 한 회의실에서 10개의 회의가 있고, 겹치지 않게 최대한 많은 회의를 배정해야 합니다.

잘못된 접근:

// ❌ 시작 시간이 빠른 순으로 선택 → 최적 아님
// 예: [1,10], [2,3], [4,5] → [1,10] 선택 시 [2,3], [4,5] 못 넣음
std::sort(meetings.begin(), meetings.end(),
     { return a.start < b.start; });

해결: 종료 시간이 빠른 순으로 정렬 후, 겹치지 않으면 선택. O(n log n).

시나리오 2: 분수 배낭 — 물건을 쪼갤 수 있을 때

상황: 배낭 용량이 50kg이고, (가치, 무게) 쌍의 물건들이 있습니다. 물건을 일부만 넣을 수 있습니다.

잘못된 접근: 0-1 배낭 문제처럼 DP를 쓰면 과한 복잡도. 분수 배낭은 탐욕으로 O(n log n)에 해결 가능.

해결: 단위 무게당 가치(가치/무게)가 높은 순으로 정렬 후, 용량이 찰 때까지 넣습니다.

시나리오 3: 거스름돈 — 동전 개수 최소화

상황: 800원을 거슬러 줄 때, 500원·100원·50원·10원 동전을 최소 개수로 주려면?

주의: 한국 동전 체계(500, 100, 50, 10)에서는 탐욕이 최적이지만, 일반적인 동전 체계에서는 탐욕이 실패할 수 있습니다. 예: {1, 3, 4}원으로 6원 → 탐욕 4+1+1=3개, 최적 3+3=2개.

해결: 동전 체계가 “캐넌리컬(canonical)“인지 확인. 한국 원화는 캐넌리컬이므로 탐욕 사용 가능.

시나리오 4: 작업 스케줄링 — 지연 시간 최소화

상황: n개의 작업이 있고, 각각 데드라인과 처리 시간이 있습니다. 한 번에 하나씩 순서대로 처리할 때, 총 지연 시간을 최소화하려면?

해결: 데드라인이 빠른 순으로 정렬 후 순서대로 처리. 탐욕이 최적을 보장합니다.

시나리오 5: 허프만 코딩 — 압축

상황: 문자 빈도가 다른 텍스트를 비트로 압축할 때, 자주 나오는 문자에 짧은 코드를 부여하려면?

해결: 허프만 트리 — 빈도가 낮은 것부터 합쳐서 이진 트리를 만들고, 트리 경로로 코드 부여. 탐욕이 최적 압축을 보장합니다.

시나리오 6: 최소 스패닝 트리 (MST)

상황: 그래프의 모든 정점을 연결하는 최소 비용 트리를 찾아야 합니다.

해결: 크루스칼 — 가중치가 작은 간선부터 선택(사이클 만들지 않을 때만). 프림 — 한 정점에서 시작해 가장 가까운 정점을 반복적으로 추가. 둘 다 탐욕 알고리즘입니다.

시나리오 7: 점프 게임 — 도달 가능 여부

상황: 배열의 각 원소가 “그 위치에서 점프할 수 있는 최대 거리”일 때, 마지막 인덱스에 도달할 수 있는지 판단해야 합니다.

해결: 탐욕 — 현재 도달 가능한 최대 인덱스를 유지하면서, 각 단계에서 max(reach, i + nums[i])로 갱신. reach >= n-1이면 도달 가능.

시나리오 8: 리소스 할당 — 강의실/서버 배정

상황: 요청들이 (시작, 종료) 시간으로 들어올 때, 모든 요청을 수용하는 최소 리소스 수를 구해야 합니다.

해결: 이벤트 스캔 — 시작/종료를 이벤트로 정렬하고, 시작 시 +1, 종료 시 -1. 동시 사용 최대치가 최소 필요 리소스 수.

알고리즘 선택 가이드

문제 유형	탐욕 적용	정렬/선택 기준	비고
활동 선택	✅	종료 시간 오름차순	최대 활동 수
분수 배낭	✅	가치/무게 내림차순	물건 쪼갤 수 있을 때
0-1 배낭	❌	DP 필요	물건 쪼갤 수 없음
거스름돈	조건부	큰 동전 우선	캐넌리컬일 때만
작업 스케줄링	✅	데드라인 오름차순	지연 최소화
허프만 코딩	✅	빈도 낮은 것부터 합침	압축

2. 탐욕법 핵심 개념

탐욕 선택 속성 (Greedy Choice Property)

정의: 전역 최적해에, 매 단계의 지역 최적 선택이 포함될 수 있다면 “탐욕 선택 속성”을 만족합니다.

flowchart LR
  A[지역 최적 선택] --> B[전역 최적해에 포함 가능]
  B --> C[탐욕법 적용 가능]

최적 부분 구조 (Optimal Substructure)

정의: 문제의 최적해가 부분 문제의 최적해들로 구성되면 “최적 부분 구조”를 가집니다. DP와 공통점이지만, 탐욕은 한 가지 부분 최적해만 선택합니다.

탐욕 vs 동적 계획법

항목	탐욕법	동적 계획법
선택	매 단계 1가지	여러 후보 검토
하위 문제	재귀적으로 1개만	여러 하위 문제
복잡도	보통 O(n log n)	보통 O(n²) 이상
증명	탐욕 선택·최적 부분 구조	중복 하위 문제

3. 완전한 탐욕 알고리즘 예제

3.1 활동 선택 (Activity Selection)

문제: n개의 활동 [시작, 종료]가 주어질 때, 겹치지 않게 최대 몇 개를 선택할 수 있는가?

탐욕 전략: 종료 시간이 빠른 순으로 정렬 후, 이전 선택과 겹치지 않으면 선택.

#include <vector>
#include <algorithm>

struct Activity {
    int start, finish;
};

// 종료 시간 기준 오름차순 정렬
std::vector<Activity> maxActivities(std::vector<Activity> activities) {
    if (activities.empty()) return {};

    std::sort(activities.begin(), activities.end(),
         {
            return a.finish < b.finish;
        });

    std::vector<Activity> result;
    result.push_back(activities[0]);
    int lastFinish = activities[0].finish;

    for (size_t i = 1; i < activities.size(); ++i) {
        if (activities[i].start >= lastFinish) {
            result.push_back(activities[i]);
            lastFinish = activities[i].finish;
        }
    }
    return result;
}

// 사용 예시
void example_activity_selection() {
    std::vector<Activity> acts = {{1,4}, {3,5}, {0,6}, {5,7}, {3,9}, {5,9}, {6,10}, {8,11}, {8,12}, {2,14}, {12,16}};
    auto selected = maxActivities(acts);
    // selected: {1,4}, {5,7}, {8,11}, {12,16} 등 — 최대 4개
}

시간 복잡도: O(n log n) (정렬) + O(n) (선택) = O(n log n).

3.2 분수 배낭 (Fractional Knapsack)

문제: 용량 W의 배낭에 (가치, 무게) 물건들을 넣을 때, 물건을 쪼갤 수 있으면 최대 가치를 구하라.

탐욕 전략: 단위 무게당 가치(가치/무게)가 높은 순으로 정렬 후, 용량이 찰 때까지 넣습니다.

#include <vector>
#include <algorithm>

struct Item {
    int value, weight;
    double valuePerUnit() const { return static_cast<double>(value) / weight; }
};

double fractionalKnapsack(std::vector<Item> items, int capacity) {
    std::sort(items.begin(), items.end(),
         {
            return a.valuePerUnit() > b.valuePerUnit();
        });

    double totalValue = 0.0;
    for (const auto& item : items) {
        if (capacity <= 0) break;
        int take = std::min(item.weight, capacity);
        totalValue += take * item.valuePerUnit();
        capacity -= take;
    }
    return totalValue;
}

// 사용 예시
void example_fractional_knapsack() {
    std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int cap = 50;
    double maxVal = fractionalKnapsack(items, cap);  // 240.0
}

시간 복잡도: O(n log n).

3.3 거스름돈 (Coin Change — Greedy)

주의: 동전 체계가 캐넌리컬일 때만 탐욕이 최적입니다. 한국 원화(500,100,50,10)는 캐넌리컬입니다.

#include <vector>

// 큰 동전부터 사용 (캐넌리컬 동전 체계 가정)
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;  // 정확히 못 맞추면 -1
}

// 사용 예시 (한국 동전)
void example_coin_change() {
    std::vector<int> coins = {500, 100, 50, 10};
    int n = coinChangeGreedy(coins, 800);  // 800 = 500+100+100+100 → 4개
}

3.4 작업 스케줄링 (Job Scheduling — 최소 지연)

문제: 각 작업에 (처리 시간, 데드라인)이 있을 때, 순서를 정해 데드라인 초과 합을 최소화.

탐욕 전략: 데드라인이 빠른 순으로 정렬 후 순서대로 처리.

#include <vector>
#include <algorithm>

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

int minTotalLateness(std::vector<Job> jobs) {
    std::sort(jobs.begin(), jobs.end(),
         { return a.deadline < b.deadline; });

    int currentTime = 0;
    int totalLateness = 0;
    for (const auto& j : jobs) {
        currentTime += j.duration;
        int lateness = std::max(0, currentTime - j.deadline);
        totalLateness += lateness;
    }
    return totalLateness;
}

3.5 회의실 II — 최소 회의실 수

문제: 겹치는 회의들을 모두 수용하려면 최소 몇 개의 회의실이 필요한가?

탐욕 전략: 시작/종료 이벤트를 시간순으로 정렬하고, 시작이면 +1, 종료면 -1. 동시에 열린 최대 회의 수가 답.

#include <vector>
#include <algorithm>

int minMeetingRooms(std::vector<std::pair<int,int>> meetings) {
    std::vector<std::pair<int,int>> events;
    for (const auto& m : meetings) {
        events.push_back({m.first, 1});   // 시작
        events.push_back({m.second, -1}); // 종료
    }
    std::sort(events.begin(), events.end(),
         {
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second;  // 종료 먼저 (같은 시각)
        });

    int rooms = 0, maxRooms = 0;
    for (const auto& e : events) {
        rooms += e.second;
        maxRooms = std::max(maxRooms, rooms);
    }
    return maxRooms;
}

3.6 크루스칼 알고리즘 (MST)

문제: 가중 그래프에서 모든 정점을 연결하는 최소 비용 트리.

탐욕 전략: 가중치가 작은 간선부터 선택. 사이클을 만들면 스킵. Union-Find로 사이클 검사.

#include <vector>
#include <algorithm>

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& e) const { return weight < e.weight; }
};

class UnionFind {
    std::vector<int> parent;
public:
    explicit UnionFind(int n) : parent(n) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        return true;
    }
};

int kruskalMST(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end());
    UnionFind uf(n);
    int totalWeight = 0;
    for (const auto& e : edges) {
        if (uf.unite(e.u, e.v)) {
            totalWeight += e.weight;
        }
    }
    return totalWeight;
}

3.7 허프만 코딩 (Huffman Coding)

문제: 문자 빈도가 주어질 때, 빈도가 높은 문자에 짧은 비트 코드를 부여해 평균 비트 수를 최소화.

탐욕 전략: 빈도가 낮은 두 노드를 반복적으로 합쳐 이진 트리를 만듭니다. 우선순위 큐 사용.

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

struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    Node(Node* l, Node* r) : ch(0), freq(l->freq + r->freq), left(l), right(r) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) { return a->freq > b->freq; }
};

void buildCodes(Node* root, const std::string& code,
                std::unordered_map<char, std::string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->ch] = code.empty() ? "0" : code;
        return;
    }
    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

std::unordered_map<char, std::string> huffmanCodes(
    const std::unordered_map<char, int>& freq) {
    std::priority_queue<Node*, std::vector<Node*>, Compare> pq;
    for (const auto& p : freq)
        pq.push(new Node(p.first, p.second));

    while (pq.size() > 1) {
        Node* l = pq.top(); pq.pop();
        Node* r = pq.top(); pq.pop();
        pq.push(new Node(l, r));
    }

    Node* root = pq.top();
    std::unordered_map<char, std::string> codes;
    buildCodes(root, "", codes);
    // 메모리 해제 생략 (실제로는 트리 순회로 delete)
    return codes;
}

3.8 구간 병합 (Merge Intervals)

문제: 겹치는 구간들을 병합하여 최소 개수의 겹치지 않는 구간으로 만들기.

탐욕 전략: 시작 시간 기준 정렬 후, 이전 구간과 겹치면 병합, 아니면 새 구간 추가.

#include <vector>
#include <algorithm>

std::vector<std::pair<int,int>> mergeIntervals(
    std::vector<std::pair<int,int>> intervals) {
    if (intervals.empty()) return {};

    std::sort(intervals.begin(), intervals.end());

    std::vector<std::pair<int,int>> result;
    result.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        auto& last = result.back();
        if (intervals[i].first <= last.second) {
            last.second = std::max(last.second, intervals[i].second);
        } else {
            result.push_back(intervals[i]);
        }
    }
    return result;
}

3.9 점프 게임 (Jump Game)

문제: nums[i]가 위치 i에서 점프할 수 있는 최대 거리일 때, 마지막 인덱스에 도달 가능한지 판단.

탐욕 전략: 도달 가능한 최대 인덱스를 유지하면서, 각 위치에서 reach = max(reach, i + nums[i])로 갱신.

#include <vector>

bool canJump(const std::vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        if (i > reach) return false;  // 여기서 도달 불가
        reach = std::max(reach, i + nums[i]);
        if (reach >= static_cast<int>(nums.size()) - 1) return true;
    }
    return true;
}

// 최소 점프 횟수 (Jump Game II)
int jump(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    if (n <= 1) return 0;
    int jumps = 0, curEnd = 0, curFarthest = 0;
    for (int i = 0; i < n - 1; ++i) {
        curFarthest = std::max(curFarthest, i + nums[i]);
        if (i == curEnd) {
            ++jumps;
            curEnd = curFarthest;
        }
    }
    return jumps;
}

3.10 레몬에이드 거스름돈 (Lemonade Change)

문제: 5원, 10원, 20원만 받을 때, 거스름돈을 올바르게 줄 수 있는지 판단. (5원만 줌)

탐욕 전략: 20원 받으면 10+5 우선, 없으면 5+5+5. 10원 받으면 5원만.

#include <vector>

bool lemonadeChange(const std::vector<int>& bills) {
    int five = 0, ten = 0;
    for (int b : bills) {
        if (b == 5) ++five;
        else if (b == 10) {
            if (five == 0) return false;
            --five; ++ten;
        } else {  // 20
            if (ten > 0 && five > 0) { --ten; --five; }
            else if (five >= 3) five -= 3;
            else return false;
        }
    }
    return true;
}

4. 증명 기법

4.1 탐욕 선택이 항상 안전함을 보이기

활동 선택 예: “종료 시간이 가장 빠른 활동 a를 포함하는 최적해가 존재한다”를 보이면 됩니다.

증명 스케치: 최적해 O가 a를 포함하지 않는다고 하자. O에서 첫 활동을 a로 교체해도 나머지 활동들과 겹치지 않는다(왜냐하면 a의 종료가 가장 빠르므로). 따라서 a를 포함하는 최적해가 존재.

// 증명의 핵심: 첫 활동을 "종료 가장 빠른 것"으로 바꿔도
// 나머지 선택에 영향 없음 → 탐욕 선택이 안전

4.2 최적 부분 구조

정의: 선택 후 남은 부분 문제가 원래 문제와 같은 형태이면 최적 부분 구조를 가집니다.

활동 선택: 첫 활동 a 선택 후, a와 겹치지 않는 활동들만 남음. 이 부분 문제의 최적해 + {a}가 전체 최적해.

4.3 교체 논법 (Exchange Argument)

아이디어: 탐욕 해와 최적해를 비교해, 최적해의 어떤 선택을 탐욕 선택으로 “교체”해도 해가 나빠지지 않음을 보입니다.

분수 배낭: 최적해 O와 탐욕 해 G를 비교. O에서 G에 없는 물건이 있다면, 그 물건의 단위 가치는 G에서 채운 물건보다 낮음. 따라서 O의 그 부분을 G의 선택으로 교체해도 가치가 줄지 않음.

4.4 매트로이드 (Matroid)

정의: 탐욕이 항상 최적인 구조를 수학적으로 정의한 것. 유한 매트로이드에서는 탐욕이 최적 가중치 기저를 줍니다.

활동 선택은 인터벌 스케줄링 매트로이드의 예입니다. 매트로이드 이론을 알면 “왜 탐욕이 되는가”를 체계적으로 이해할 수 있습니다.

4.5 귀납법 (Induction)

아이디어: k번째 탐욕 선택까지의 부분 해가 최적해의 접두사와 일치함을 귀납적으로 보입니다.

기저: k=0일 때, 빈 선택은 최적해의 접두사와 일치.
귀납: k번째까지 최적해 접두사와 일치한다고 가정. k+1번째 탐욕 선택은 “탐욕 선택 속성”에 의해 최적해에 포함 가능. 따라서 k+1번째까지도 일치.

4.6 증명 체크리스트

탐욕 알고리즘을 설계할 때 다음을 확인합니다:

항목	확인 방법
탐욕 선택 속성	”첫 선택을 탐욕 선택으로 바꿔도 최적해 존재”
최적 부분 구조	”선택 후 남은 문제가 최적 부분 구조”
반례 검사	”다른 정렬 기준이 더 나은 예가 있는가?”
경계 케이스	빈 입력, 단일 원소, 모두 겹침 등

5. 자주 발생하는 에러와 해결법

문제 1: 잘못된 정렬 기준

증상: 활동 선택에서 “시작 시간”으로 정렬하면 최적이 아닌 경우가 있습니다.

// ❌ 잘못된 정렬
std::sort(activities.begin(), activities.end(),
     {
        return a.start < b.start;  // 최적 아님!
    });

// ✅ 올바른 정렬 — 종료 시간
std::sort(activities.begin(), activities.end(),
     {
        return a.finish < b.finish;
    });

문제 2: 0-1 배낭에 탐욕 적용

증상: 물건을 쪼갤 수 없는 0-1 배낭에서 “가치/무게” 순 탐욕을 쓰면 최적이 아닙니다.

// ❌ 분수 배낭 전략을 0-1 배낭에 적용
// 예: 용량 50, (60,10), (100,20), (120,30)
// 탐욕: 60+100=160 (30kg 남음, 120 못 넣음)
// 최적: 100+120=220 (20+30=50kg)

// ✅ 0-1 배낭은 DP 사용
// dp[i][w] = i번째까지 고려, 용량 w에서 최대 가치

문제 3: 비캐넌리컬 동전에서 탐욕

증상: {1, 3, 4}원으로 6원을 만들 때, 탐욕은 4+1+1=3개지만 최적은 3+3=2개입니다.

// ❌ 탐욕 (실패)
std::vector<int> coins = {1, 3, 4};
int amount = 6;
// 탐욕: 4, 1, 1 → 3개
// 최적: 3, 3 → 2개

// ✅ DP로 최소 동전 수
int coinChangeDP(std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int c : coins) {
            if (i >= c) dp[i] = std::min(dp[i], dp[i - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

문제 4: 비교자에서 등호 처리

증상: 정렬 시 a.finish <= b.finish처럼 등호를 넣으면, 같은 종료 시간일 때 순서가 불안정해질 수 있습니다.

// ❌ 등호 사용 시 불안정
std::sort(activities.begin(), activities.end(),
     {
        return a.finish <= b.finish;  // strict weak ordering 위반 가능
    });

// ✅ strict weak ordering: < 만 사용
std::sort(activities.begin(), activities.end(),
     {
        return a.finish < b.finish;
    });

문제 5: 구간 병합 시 경계 처리

증상: [1,4]와 [4,5]는 겹친다고 봐야 합니다. <= vs < 혼동.

// ❌ 잘못된 겹침 검사
if (intervals[i].first < last.second)  // [4,5]와 [1,4]가 안 겹친다고 봄

// ✅ 올바른 겹침 검사
if (intervals[i].first <= last.second)  // [4,5]와 [1,4]는 겹침

문제 6: 허프만 트리 메모리 누수

증상: new로 만든 노드를 해제하지 않으면 메모리 누수.

// ✅ 트리 해제 헬퍼
void deleteTree(Node* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

문제 7: 점프 게임에서 인덱스 오버플로우

증상: i + nums[i]가 int 범위를 넘을 수 있습니다. (드물지만)

// ❌ 오버플로우 가능 (nums[i]가 매우 클 때)
reach = std::max(reach, i + nums[i]);

// ✅ long long 또는 범위 검사
reach = std::max(reach, std::min(i + nums[i], n - 1));

문제 8: 구간 정렬 시 동일 시작 시간

증상: [1,4], [1,2]처럼 시작이 같을 때, [1,2]를 먼저 처리해야 병합이 올바릅니다.

// ✅ 시작 같으면 종료 빠른 것 먼저 (더 짧은 구간 먼저)
std::sort(intervals.begin(), intervals.end(),
     {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });

6. 성능 최적화 팁

1. 정렬 한 번만

탐욕 알고리즘은 대부분 정렬이 지배적입니다. O(n log n) 정렬 후 O(n) 스캔이면 충분합니다.

// ✅ 한 번 정렬 후 선형 스캔
std::sort(items.begin(), items.end(), compare);
for (const auto& x : items) { /* O(n) */ }

2. 인덱스만 정렬 (원본 유지)

원본을 바꾸지 않고 인덱스만 정렬하면, 여러 기준으로 재사용할 수 있습니다.

std::vector<size_t> sortIndices(const std::vector<Activity>& acts) {
    std::vector<size_t> idx(acts.size());
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(idx.begin(), idx.end(),
        [&acts](size_t a, size_t b) {
            return acts[a].finish < acts[b].finish;
        });
    return idx;
}

3. 우선순위 큐 활용

허프만, 다익스트라 등에서는 std::priority_queue가 핵심입니다.

std::priority_queue<Node*, std::vector<Node*>, Compare> pq;
// 삽입 O(log n), 최소 추출 O(log n)

4. Union-Find 경로 압축

크루스칼에서 Union-Find의 경로 압축이 없으면 거의 선형에 가깝게 느려질 수 있습니다.

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);  // 경로 압축
    return parent[x];
}

5. 벤치마크 참고 (n=10만)

알고리즘	시간 (대략)
활동 선택	~15ms
분수 배낭	~18ms
크루스칼 (간선 50만)	~80ms
구간 병합	~12ms

7. 프로덕션 패턴

1. 탐욕 선택기 추상화

template<typename T, typename Compare>
std::vector<T> greedySelect(std::vector<T> items, Compare comp) {
    std::sort(items.begin(), items.end(), comp);
    std::vector<T> result;
    for (const auto& x : items) {
        if (canAdd(result, x)) result.push_back(x);
    }
    return result;
}

2. 검증 함수

탐욕 결과가 제약 조건을 만족하는지 검증합니다.

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;
}

3. 캐넌리컬 동전 체계 검사

// 간단한 휴리스틱: 작은 동전이 큰 동전의 약수가 아니면 비캐넌리컬일 수 있음
bool isCanonical(const std::vector<int>& coins) {
    // 완전한 검사는 더 복잡 (DP로 1..2*max 검사 등)
    for (size_t i = 1; i < coins.size(); ++i) {
        if (coins[i] % coins[i-1] != 0) return false;  // 단순 휴리스틱
    }
    return true;
}

4. 로깅 및 디버깅

#ifdef DEBUG_GREEDY
#define LOG_GREEDY(msg) std::cerr << "[GREEDY] " << msg << "\n"
#else
#define LOG_GREEDY(msg) ((void)0)
#endif

// 활동 선택 시
LOG_GREEDY("Selected activity [" << a.start << "," << a.finish << "]");

5. 단위 테스트 패턴

void test_activity_selection() {
    std::vector<Activity> acts = {{1,2}, {2,3}, {3,4}};
    auto result = maxActivities(acts);
    assert(result.size() == 3);
    assert(validateActivities(result));
}

8. 구현 체크리스트

탐욕 적용 전

탐욕 선택 속성이 성립하는지 확인
최적 부분 구조가 있는지 확인
반례(탐욕이 실패하는 예)가 없는지 검토

정렬 기준

활동 선택: 종료 시간 오름차순
분수 배낭: 가치/무게 내림차순
작업 스케줄링: 데드라인 오름차순
구간 병합: 시작 시간 오름차순

주의 사항

0-1 배낭에는 탐욕 사용 금지 (DP)
거스름돈: 동전 체계가 캐넌리컬인지 확인
비교자 strict weak ordering 준수

프로덕션

결과 검증 함수 추가
경계 케이스 (빈 입력, 단일 원소) 테스트
메모리 해제 (허프만 트리 등)

정리

항목	설명
활동 선택	종료 시간 오름차순, O(n log n)
분수 배낭	가치/무게 내림차순, O(n log n)
0-1 배낭	탐욕 불가, DP 사용
거스름돈	캐넌리컬일 때만 탐욕
작업 스케줄링	데드라인 오름차순
크루스칼	가중치 오름차순 + Union-Find
허프만	빈도 낮은 것부터 합침

핵심 원칙:

탐욕이 최적인지 증명 또는 검증 후 사용
정렬 기준을 문제에 맞게 선택
0-1 배낭·비캐넌리컬 동전에는 탐욕 사용 금지
프로덕션에서는 검증·로깅 추가

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 작업 스케줄링, 리소스 할당, 데이터 압축(허프만), 네트워크 MST, 캐시 교체(LRU) 등에 활용합니다. 다익스트라 최단 경로도 탐욕 알고리즘입니다.

Q. 선행으로 읽으면 좋은 글은?

A. 정렬, 우선순위 큐, 동적 계획법 기초를 먼저 익히면 탐욕법과의 차이를 이해하기 쉽습니다.

Q. 더 깊이 공부하려면?

A. LeetCode Greedy 유형, 《알고리즘 설계》 탐욕법 챕터, 매트로이드 이론을 참고하세요.

한 줄 요약: 탐욕법은 “매 순간 최선”이 전역 최적을 보장할 때만 사용하고, 활동 선택·분수 배낭·스케줄링 등에서 정렬 기준을 정확히 적용해야 합니다.

부록: 탐욕 알고리즘 복잡도 요약

알고리즘	시간	공간	비고
활동 선택	O(n log n)	O(1)	정렬 지배
분수 배낭	O(n log n)	O(1)	정렬 지배
거스름돈 (캐넌리컬)	O(n log n)	O(1)	정렬
작업 스케줄링	O(n log n)	O(1)	정렬
구간 병합	O(n log n)	O(n)	결과 저장
점프 게임	O(n)	O(1)	정렬 불필요
회의실 II	O(n log n)	O(n)	이벤트 정렬
크루스칼 MST	O(E log E)	O(V)	Union-Find
허프만 코딩	O(n log n)	O(n)	우선순위 큐
다익스트라	O((V+E) log V)	O(V)	우선순위 큐

참고 자료

LeetCode Greedy
GeeksforGeeks: Greedy Algorithms
《알고리즘 설계》 — Kleinberg, Tardos
《Introduction to Algorithms》 (CLRS) — Greedy Algorithms 챕터

C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]
C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
C++ 알고리즘 |