그리디 알고리즘 패턴과 증명 전략

개요

그리디(Greedy) 알고리즘은 각 단계에서 현재 최선의 선택을 하여 전체 최적해를 구하는 방법입니다. 동적 계획법보다 구현이 단순하고 빠르지만, 두 가지 속성이 성립할 때만 올바른 결과를 보장합니다.

1. 그리디가 유효한 조건

1. 탐욕 선택 속성 (Greedy Choice Property):
   각 단계의 탐욕적 선택이 전체 최적해를 포함한다.

2. 최적 부분 구조 (Optimal Substructure):
   전체 최적해가 부분 문제의 최적해를 포함한다.

2. 활동 선택 문제

struct Activity {
    int start, end, id;
};

// 종료 시간 기준 그리디: 가장 일찍 끝나는 활동 우선 선택
std::vector<int> SelectActivities(std::vector<Activity>& acts) {
    std::sort(acts.begin(), acts.end(),
        [](const Activity& a, const Activity& b) {
            return a.end < b.end; // 종료 시간 오름차순
        });

    std::vector<int> selected;
    int lastEnd = -1;

    for (const Activity& a : acts) {
        if (a.start >= lastEnd) {
            selected.push_back(a.id);
            lastEnd = a.end;
        }
    }

    return selected;
}

// 증명: 가장 일찍 끝나는 활동을 선택해도 최적해 손실 없음
// → 귀류법으로 증명 (종료 안한 활동 교체 시 결과 동일 또는 개선)

3. 거스름돈 문제

// 동전 단위: {500, 100, 50, 10, 5, 1}
// 그리디: 항상 옳음 (동전 단위가 서로 배수 관계)
std::vector<std::pair<int,int>> MakeChange(
    int amount, std::vector<int> coins)
{
    std::sort(coins.begin(), coins.end(), std::greater<int>());

    std::vector<std::pair<int,int>> result;
    for (int coin : coins) {
        if (amount >= coin) {
            result.push_back({coin, amount / coin});
            amount %= coin;
        }
    }
    return result;
}

// ⚠️ 단위가 배수 관계가 아니면 그리디 실패!
// {1, 3, 4}원으로 6원 만들기:
// 그리디: 4+1+1 = 3개 (잘못됨)
// 최적:   3+3   = 2개 (맞음)
// → 이 경우 DP 사용 필요

4. 허프만 코딩

#include <queue>

struct HuffNode {
    char ch;
    int freq;
    HuffNode* left = nullptr;
    HuffNode* right = nullptr;

    bool operator>(const HuffNode& o) const { return freq > o.freq; }
};

HuffNode* BuildHuffmanTree(const std::map<char, int>& freqs) {
    std::priority_queue<HuffNode*,
        std::vector<HuffNode*>,
        [](HuffNode* a, HuffNode* b){ return a->freq > b->freq; }> pq;

    for (const auto& [ch, f] : freqs)
        pq.push(new HuffNode{ch, f});

    while (pq.size() > 1) {
        // 빈도 낮은 두 노드 합침
        auto* left  = pq.top(); pq.pop();
        auto* right = pq.top(); pq.pop();

        auto* merged = new HuffNode{'\0', left->freq + right->freq};
        merged->left  = left;
        merged->right = right;
        pq.push(merged);
    }

    return pq.top();
}

5. 작업 스케줄링 — 마감 시간

struct Job {
    int id;
    int deadline;
    int profit;
};

// 이익 기준 내림차순으로 작업 선택
int JobScheduling(std::vector<Job>& jobs) {
    std::sort(jobs.begin(), jobs.end(),
        [](const Job& a, const Job& b){ return a.profit > b.profit; });

    int maxDeadline = 0;
    for (const Job& j : jobs) maxDeadline = std::max(maxDeadline, j.deadline);

    std::vector<int> slots(maxDeadline + 1, -1); // -1: 빈 슬롯
    int totalProfit = 0;

    for (const Job& j : jobs) {
        // 마감 시간 직전 빈 슬롯 찾기
        for (int t = j.deadline; t >= 1; t--) {
            if (slots[t] == -1) {
                slots[t] = j.id;
                totalProfit += j.profit;
                break;
            }
        }
    }

    return totalProfit;
}

6. 그리디 실패 케이스

// ❌ 0/1 배낭 문제 (Fractional Knapsack은 OK)
// 무게/가치 비율로 탐욕 선택 → 최적 아닐 수 있음
// → DP 필요

// ❌ 최단 경로 (음수 가중치 있는 경우)
// 다익스트라는 양수 가중치에서만 올바름
// → Bellman-Ford 필요

// ❌ 동전 문제 (비표준 단위)
// {1, 3, 4}로 6 만들기: 그리디 실패
// → DP 필요

7. 게임 개발 활용

// AI 행동 선택 — 즉각 최선의 행동
int SelectBestAction(const std::vector<Action>& actions,
                     const GameState& state)
{
    // 각 행동의 즉각 이득 계산 후 최대 선택
    return std::max_element(actions.begin(), actions.end(),
        [&](const Action& a, const Action& b) {
            return EvaluateImmediate(a, state) < EvaluateImmediate(b, state);
        }) - actions.begin();
}

// 자원 배분 — 남은 자원을 가장 효율 좋은 곳에 배분
void AllocateResources(int budget, std::vector<Building>& buildings) {
    std::sort(buildings.begin(), buildings.end(),
        [](const Building& a, const Building& b) {
            return (float)a.value / a.cost > (float)b.value / b.cost;
        });

    for (auto& b : buildings) {
        if (budget >= b.cost) {
            b.built = true;
            budget -= b.cost;
        }
    }
}

정리

탐욕 선택 속성 + 최적 부분 구조 → 그리디 적용 가능
활동 선택, 허프만 코딩, 분할 가능 배낭, 프림/다익스트라
0/1 배낭, 음수 가중치 최단 경로, 비표준 동전 → 그리디 실패
올바른 그리디 알고리즘에는 반드시 정확성 증명 필요

참고 자료

Introduction to Algorithms (CLRS) — Chapter 16