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

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

실제 겪는 문제 시나리오

탐욕 알고리즘(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번째 탐욕 선택까지의 부분 해가 최적해의 접두사와 일치함을 귀납적으로 보입니다.

1. 기저: k=0일 때, 빈 선택은 최적해의 접두사와 일치.
2. 귀납: 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
허프만	빈도 낮은 것부터 합침
핵심 원칙:

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

---

자주 묻는 질문 (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)	우선순위 큐

---

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

참고 자료

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

---

관련 글

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

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

이 부록은 앞선 본문에서 다룬 주제(「C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·배낭·스케줄링·증명 기법 [실전]」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(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++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·배낭·스케줄링·증명 기법 [실전]」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

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

---

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

C++, 탐욕법, Greedy, 알고리즘, 활동선택, 스케줄링 등으로 검색하시면 이 글이 도움이 됩니다.