그리디 알고리즘

그리디 알고리즘이란

그리디(Greedy) 알고리즘은 각 단계에서 현재 최선의 선택을 반복해 전체 최적해를 구하는 방법입니다.

정당성 조건 (두 가지 중 하나 필요):

• 탐욕 선택 속성: 지역 최적이 전역 최적에 기여
• 최적 부분 구조: 부분 문제의 최적해가 전체 최적해에 포함

활동 선택 문제 (Activity Selection)

종료 시간 기준 정렬 후 겹치지 않는 최대 활동 수 선택.

struct Activity { int start, end; };

int activitySelection(vector<Activity>& acts) {
    sort(acts.begin(), acts.end(),
         [](const Activity& a, const Activity& b){ return a.end < b.end; });

    int count = 1;
    int lastEnd = acts[0].end;

    for (int i = 1; i < (int)acts.size(); i++) {
        if (acts[i].start >= lastEnd) {
            count++;
            lastEnd = acts[i].end;
        }
    }
    return count;
}

정당성: 종료가 가장 빠른 활동을 선택하면 남은 시간이 최대 → 교환 논증으로 증명.

허프만 코딩 (Huffman Coding)

최적 접두어 코드 생성. 빈도 낮은 문자에 긴 코드 배정.

struct HuffNode {
    char ch;
    int freq;
    HuffNode *left, *right;
    HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

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

HuffNode* buildHuffman(map<char, int>& freq) {
    priority_queue<HuffNode*, vector<HuffNode*>, Compare> pq;
    for (auto& [ch, f] : freq)
        pq.push(new HuffNode(ch, f));

    while (pq.size() > 1) {
        HuffNode* left  = pq.top(); pq.pop();
        HuffNode* right = pq.top(); pq.pop();
        HuffNode* merged = new HuffNode('\0', left->freq + right->freq);
        merged->left  = left;
        merged->right = right;
        pq.push(merged);
    }
    return pq.top();
}

void generateCodes(HuffNode* node, string code, map<char, string>& codes) {
    if (!node) return;
    if (node->ch != '\0') { codes[node->ch] = code; return; }
    generateCodes(node->left,  code + "0", codes);
    generateCodes(node->right, code + "1", codes);
}

회의실 배정 (최소 회의실 수)

동시에 진행되는 회의 최대 수 = 필요한 회의실 수.

int minMeetingRooms(vector<pair<int,int>>& intervals) {
    vector<int> starts, ends;
    for (auto& [s, e] : intervals) { starts.push_back(s); ends.push_back(e); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int rooms = 0, maxRooms = 0;
    int j = 0;
    for (int i = 0; i < (int)starts.size(); i++) {
        if (starts[i] < ends[j]) rooms++;
        else j++;
        maxRooms = max(maxRooms, rooms);
    }
    return maxRooms;
}

배낭 문제: 분수형 (Fractional Knapsack)

0/1 배낭은 DP, 분수형은 그리디로 최적해 보장.

struct Item { double weight, value; };

double fractionalKnapsack(vector<Item>& items, double capacity) {
    sort(items.begin(), items.end(),
         [](const Item& a, const Item& b){
             return a.value / a.weight > b.value / b.weight;  // 단위 가치 내림차순
         });

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

다익스트라 (Dijkstra)

단일 출발점 최단 경로. 음수 간선 없을 때 O((V+E) log V).

vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj, int n) {
    const long long INF = 1e18;
    vector<long long> dist(n, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 이미 처리된 노드

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

크루스칼 (Kruskal MST)

최소 신장 트리. 간선 정렬 + Union-Find. O(E log E).

struct Edge { int u, v, w; };
struct UnionFind {
    vector<int> parent, rank_;
    UnionFind(int n) : parent(n), rank_(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }
};

long long kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.w < b.w; });
    UnionFind uf(n);
    long long mstWeight = 0;
    int edgeCount = 0;

    for (auto& [u, v, w] : edges) {
        if (uf.unite(u, v)) {
            mstWeight += w;
            if (++edgeCount == n - 1) break;
        }
    }
    return mstWeight;
}

구간 스케줄링 최적화 (Job Scheduling)

마감 시간이 있는 작업, 이익 최대화.

struct Job { int deadline, profit; };

int jobScheduling(vector<Job>& jobs, int maxDeadline) {
    sort(jobs.begin(), jobs.end(),
         [](const Job& a, const Job& b){ return a.profit > b.profit; });

    vector<int> slot(maxDeadline + 1, -1);
    int totalProfit = 0;

    for (auto& job : jobs) {
        for (int t = job.deadline; t >= 1; t--) {
            if (slot[t] == -1) {
                slot[t] = job.profit;
                totalProfit += job.profit;
                break;
            }
        }
    }
    return totalProfit;
}

그리디 vs DP

특성	그리디	DP
선택 방식	현재 최선 (되돌림 없음)	모든 경우 고려
시간 복잡도	보통 더 빠름	더 느림
정확성	정당성 증명 필요	항상 최적
적용 예	활동 선택, MST	배낭 0/1, LCS

정리

• 탐욕 선택 속성 + 최적 부분 구조 → 그리디 적용 가능
• 활동 선택: 종료 시간 기준 정렬
• 허프만 코딩: 최소 힙으로 최적 접두어 코드
• 다익스트라: 우선순위 큐 + 탐욕적 거리 확장
• 크루스칼: 간선 정렬 + Union-Find로 MST
• 그리디가 틀린다면 DP나 백트래킹 고려