---
id: wiki-2026-0508-greedy-algorithms
title: Greedy Algorithms
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Greedy, 그리디 알고리즘, 탐욕 알고리즘]
duplicate_of: none
source_trust_level: A
confidence_score: 0.92
verification_status: applied
tags: [algorithms, greedy, optimization, matroid]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: python
  framework: none
---

# Greedy Algorithms

## 매 한 줄
> **"매 step 의 locally optimal choice 의 의 globally optimal 의 hope"**. 매 1956 Kruskal 의 MST 의 formal start. 매 modern era 의 universal — 매 Huffman, MST, scheduling, set cover (approx). 매 proof 의 critical (greedy 의 wrong 의 silent failure).

## 매 핵심

### 매 두 정당화 (matroid theory)
1. **Greedy choice property**: 매 local optimal 의 의 global optimal 의 의 contain.
2. **Optimal substructure**: 매 problem 의 reduce 의 후 의 동일 structure 의 problem.

### 매 proof technique
- **Exchange argument**: 매 OPT 의 greedy choice 의 swap 의 의 worse X.
- **Matroid theory**: 매 independence system 의 matroid 의 의 → greedy 의 optimal.
- **Stays ahead**: 매 greedy 의 step 의 의 OPT 의 step 의 의 dominate.

### 매 Greedy fails 의 example
- **0/1 knapsack**: greedy by value/weight ratio 의 fails — DP 의 의.
- **Coin change (arbitrary denominations)**: greedy fails (예: coins=[1,3,4], amount=6 → greedy 4+1+1=3 coins, OPT 3+3=2 coins).

### 매 응용
1. MST: Kruskal, Prim.
2. Shortest path (non-negative): Dijkstra.
3. Compression: Huffman coding.
4. Scheduling: earliest deadline first, shortest job next.
5. Approximation: set cover, vertex cover (2-approx).

## 💻 패턴

### Activity Selection (interval scheduling)
```python
def activity_selection(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Select max non-overlapping intervals. Greedy: earliest finish first."""
    intervals.sort(key=lambda x: x[1])  # sort by end time
    selected = []
    last_end = -float('inf')
    for s, e in intervals:
        if s >= last_end:
            selected.append((s, e))
            last_end = e
    return selected
# O(n log n)
```

### Huffman coding
```python
import heapq
from collections import Counter

def huffman(text: str) -> dict[str, str]:
    freq = Counter(text)
    heap = [[f, [c, ""]] for c, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]: pair[1] = '0' + pair[1]
        for pair in hi[1:]: pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return {c: code for c, code in heap[0][1:]}

print(huffman("aaabbc"))  # e.g., {'a': '0', 'b': '10', 'c': '11'}
```

### Kruskal's MST (greedy + union-find)
```python
class UF:
    def __init__(self, n): self.p = list(range(n)); self.r = [0]*n
    def find(self, x):
        while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
    """edges: (u, v, weight). Returns total MST weight."""
    edges.sort(key=lambda e: e[2])
    uf, total = UF(n), 0
    for u, v, w in edges:
        if uf.union(u, v):
            total += w
    return total
# O(E log E)
```

### Coin change (canonical, e.g., USD)
```python
def coin_change_greedy(coins: list[int], amount: int) -> int:
    """ASSUMES canonical coin system. Fails for arbitrary denominations."""
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        n, amount = divmod(amount, c)
        count += n
    return count if amount == 0 else -1
# USD [25,10,5,1] → canonical, greedy works
# [1,3,4] → NOT canonical, greedy fails for 6
```

### Set cover (approximation, ln(n) factor)
```python
def set_cover(universe: set, sets: list[set]) -> list[int]:
    """Greedy: pick set covering most uncovered. ln(n)-approx."""
    covered, picked = set(), []
    while covered != universe:
        best = max(range(len(sets)), key=lambda i: len(sets[i] - covered))
        picked.append(best)
        covered |= sets[best]
    return picked
```

## 매 결정 기준
| 상황 | Approach |
|---|---|
| 매 matroid structure 의 detect | Greedy (provably optimal) |
| 매 exchange argument 의 의 | Greedy |
| 매 NP-hard, approximation OK | Greedy (set cover, vertex cover) |
| 매 overlap subproblem | DP (greedy 의 X) |
| 매 backtrack 의 needed | Branch & Bound |
| 매 proof X | DP / brute-force 의 first |

**기본값**: 매 problem 의 simple structure 의 greedy 의 first 시도. 매 counterexample 의 found → DP / B&B.

## 🔗 Graph
- 부모: [[Optimization]]
- 응용: [[Dijkstra's Algorithm]]
- Adjacent: [[Dynamic Programming]] · [[Linear Programming]]

## 🤖 LLM 활용
**언제**: 매 simple optimization, 매 sorting + linear scan 의 의 의 의 의 의, 매 NP-hard 의 approximation 의 의, 매 streaming algorithm.
**언제 X**: 매 0/1 knapsack, 매 LCS, 매 edit distance — 매 DP 의 의. 매 counterexample 의 unsure 의 first.

## ❌ 안티패턴
- **proof X**: 매 greedy 의 silent wrong answer (coin change [1,3,4], 0/1 knapsack).
- **canonical 가정**: 매 USD coins 의 greedy works, but 매 arbitrary denominations 의 fails.
- **local minima trap**: 매 hill-climbing 의 local optimum 의 stuck — 매 simulated annealing / restart 의 의.
- **greedy + DP confusion**: 매 fractional knapsack (greedy works) vs 0/1 knapsack (DP needed).

## 🧪 검증 / 중복
- Verified (CLRS Ch 16; Kleinberg-Tardos Ch 4).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — Greedy with activity selection, Huffman, Kruskal, set cover |
