C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]

· 40분 읽기 · 수정 고급 실습
C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]

이 글의 핵심

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

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

실제 겪는 문제 시나리오

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

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

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링의 완전한 C++ 구현, 자주 하는 실수, 베스트 프랙티스, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

  • 탐욕법이 적용되는 문제와 적용되지 않는 문제를 구분할 수 있습니다.
  • 활동 선택, 분수 배낭, 허프만 코딩, 구간 스케줄링을 C++로 구현할 수 있습니다.
  • 흔한 실수를 피하고 프로덕션 수준의 코드를 작성할 수 있습니다.

요구 환경: C++17 이상

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

목차

  1. 문제 시나리오
  2. 탐욕법 핵심 개념
  3. 완전한 탐욕 알고리즘 예제
  4. 자주 발생하는 에러와 해결법
  5. 베스트 프랙티스
  6. 성능 최적화 팁
  7. 프로덕션 패턴
  8. 구현 체크리스트

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: 텍스트 압축 — 자주 나오는 문자에 짧은 코드

상황: “AAAAABBBCCD” 같은 문자열을 압축할 때, 고정 길이(각 문자 2비트) 대신 가변 길이로 평균 비트 수를 줄이려면?

해결: 허프만 코딩 — 빈도가 낮은 두 문자를 반복적으로 합쳐 이진 트리를 만들고, 빈도가 높은 문자에 짧은 비트 코드를 부여합니다.

시나리오 4: 구간 스케줄링 — 겹치는 구간 처리

상황: [1,3], [2,4], [3,5] 같은 구간들이 있을 때, (1) 겹치지 않게 최대 개수 선택, (2) 모든 구간을 수용하는 최소 리소스 수를 구해야 합니다.

해결: (1) 종료 시간 오름차순 정렬 후 탐욕 선택. (2) 시작/종료 이벤트 스캔으로 동시 사용 최대치 계산.

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

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

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

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

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

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

알고리즘 선택 가이드

flowchart LR
  A[문제 유형] --> B{물건 쪼갤 수 있나?}
  B -->|예| C[분수 배낭: 가치/무게]
  B -->|아니오| D[0-1 배낭: DP]
  A --> E{구간/활동?}
  E --> F[종료 시간 정렬]
  A --> G{압축?}
  G --> H[허프만]
문제 유형탐욕 적용정렬/선택 기준비고
활동 선택✅종료 시간 오름차순최대 활동 수
분수 배낭✅가치/무게 내림차순물건 쪼갤 수 있을 때
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의 배낭에 (가치, 무게) 물건들을 넣을 때, 물건을 쪼갤 수 있으면 최대 가치를 구하라.

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

왜 단위 가치인가? 1kg당 가치가 높은 물건을 먼저 채우면 최대 이득입니다.

#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;
    // 60/10=6, 100/20=5, 120/30=4 → 60 전체 + 100 전체 + 120의 20/30
    double maxVal = fractionalKnapsack(items, cap);  // 60+100+80 = 240.0
}

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

3.3 허프만 코딩 (Huffman Coding)

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

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

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

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

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

void buildCodes(HuffmanNode* 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<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    for (const auto& p : freq)
        pq.push(new HuffmanNode(p.first, p.second));

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

    HuffmanNode* root = pq.top();
    std::unordered_map<char, std::string> codes;
    buildCodes(root, "", codes);
    // 메모리 해제: deleteTree(root) 호출 필요
    return codes;
}

void deleteTree(HuffmanNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

// 사용 예시: "AAAAABBBCCD" → A:5, B:3, C:2, D:1
void example_huffman() {
    std::unordered_map<char, int> freq = {{'A',5}, {'B',3}, {'C',2}, {'D',1}};
    auto codes = huffmanCodes(freq);
    // A: 0, B: 10, C: 110, D: 111 등 (트리 구조에 따라 다름)
}

시간 복잡도: O(n log n). n은 고유 문자 수.

3.4 구간 스케줄링 (Interval Scheduling)

3.4.1 겹치지 않는 최대 구간 수

문제: 구간들이 주어질 때, 서로 겹치지 않게 최대 몇 개를 선택할 수 있는가?

해결: 활동 선택과 동일 — 종료 시간 오름차순 정렬 후 탐욕.

#include <vector>
#include <algorithm>

using Interval = std::pair<int, int>;

std::vector<Interval> maxNonOverlappingIntervals(
    std::vector<Interval> intervals) {
    if (intervals.empty()) return {};

    std::sort(intervals.begin(), intervals.end(),
         {
            return a.second < b.second;  // 종료 시간 기준
        });

    std::vector<Interval> result;
    result.push_back(intervals[0]);
    int lastEnd = intervals[0].second;

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].first >= lastEnd) {
            result.push_back(intervals[i]);
            lastEnd = intervals[i].second;
        }
    }
    return result;
}

3.4.2 최소 회의실 수 (모든 구간 수용)

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

탐욕 전략: 시작/종료 이벤트를 시간순으로 정렬하고, 시작이면 +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});   // 시작: +1
        events.push_back({m.second, -1}); // 종료: -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.4.3 구간 병합 (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.5 작업 스케줄링 (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.6 거스름돈 (Coin Change — Greedy)

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

#include <vector>
#include <algorithm>

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

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

문제 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: 비교자에서 등호 처리 (Strict Weak Ordering 위반)

증상: 정렬 시 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로 만든 노드를 해제하지 않으면 메모리 누수.

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

// ✅ unique_ptr 사용 시 자동 해제

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

증상: i + nums[i]가 int 범위를 넘을 수 있습니다.

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

// ✅ long long 또는 범위 검사
int n = static_cast<int>(nums.size());
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;
    });

문제 9: 빈 입력·단일 원소 미처리

증상: activities.empty() 또는 activities.size() == 1일 때 크래시 또는 잘못된 결과.

// ✅ 경계 케이스 처리
std::vector<Activity> maxActivities(std::vector<Activity> activities) {
    if (activities.empty()) return {};
    if (activities.size() == 1) return {activities[0]};
    // ...
}

5. 베스트 프랙티스

5.1 탐욕 적용 전 검증

탐욕법을 쓰기 전에 다음을 확인합니다:

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

5.2 정렬 기준 요약

활동 선택 / 구간 선택: 종료 시간 오름차순
분수 배낭: 가치/무게 내림차순
작업 스케줄링: 데드라인 오름차순
구간 병합: 시작 시간 오름차순 (같으면 종료 오름차순)
회의실 수: 이벤트 정렬 (시작 +1, 종료 -1)

5.3 탐욕 vs DP 선택 가이드

flowchart TD
  A[최적화 문제] --> B{부분 문제 중복?}
  B -->|아니오| C[탐욕 시도]
  B -->|예| D[DP]
  C --> E{탐욕 선택 속성?}
  E -->|예| F[탐욕 사용]
  E -->|아니오| D

5.4 코드 가독성

  • 비교 람다는 { return a.field < b.field; } 형태로 명확히.
  • struct에 operator< 정의보다 람다가 여러 기준 사용 시 유리.
  • 매직 넘버 대신 constexpr 또는 이름 있는 상수 사용.
constexpr int MAX_CAPACITY = 50;
double total = fractionalKnapsack(items, MAX_CAPACITY);

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. 벤치마크 참고 (n=10만)

알고리즘시간 (대략)
활동 선택~15ms
분수 배낭~18ms
구간 병합~12ms
회의실 II~14ms
허프만 (고유 문자 256)~2ms

7. 프로덕션 패턴

1. 탐욕 선택기 추상화

template<typename T, typename Compare, typename CanAdd>
std::vector<T> greedySelect(std::vector<T> items, Compare comp, CanAdd canAdd) {
    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) {
    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));
}

6. 에러 처리 및 예외

std::optional<std::vector<Activity>> maxActivitiesSafe(
    const std::vector<Activity>& activities) {
    if (activities.empty()) return std::nullopt;
    // 음수 시간 등 유효성 검사
    for (const auto& a : activities) {
        if (a.start < 0 || a.finish < a.start) return std::nullopt;
    }
    return maxActivities(activities);
}

8. 구현 체크리스트

탐욕 적용 전

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

정렬 기준

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

주의 사항

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

프로덕션

  • 결과 검증 함수 추가
  • 경계 케이스 (빈 입력, 단일 원소) 테스트
  • 메모리 해제 (허프만 트리 등)
  • 로깅/디버깅 매크로 (선택)

정리

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

핵심 원칙:

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

자주 묻는 질문 (FAQ)

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

A. 작업 스케줄링, 리소스 할당, 데이터 압축(허프만), 캐시 교체(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)결과 저장
회의실 IIO(n log n)O(n)이벤트 정렬
허프만 코딩O(n log n)O(n)우선순위 큐

참고 자료

관련 글

  • C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
  • C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어·Strassen [실전]
  • C++ 알고리즘 |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3