Greedy Algorithms & Heuristics

1. Overview

그리디 알고리즘과 휴리스틱(Greedy Algorithms & Heuristics)은 **매 순간 현재 상황에서 가장 좋아 보이는 선택(탐욕적 선택, Greedy Choice)**을 반복하여, 전체 문제의 최적해(Optimal Solution)를 구하는 알고리즘 설계 패러다임입니다.

학습자는 그리디가 동작하기 위한 두 가지 수학적 조건인 **탐욕적 선택 속성(Greedy Choice Property)**과 **최적 부분 구조(Optimal Substructure)**를 DP와의 대비 속에서 뜯어봅니다. 나아가 이 두 조건이 성립하는 고전 문제들—활동 선택(Activity Selection), 허프만 코딩(Huffman Coding), 크루스칼/프림 MST(Minimum Spanning Tree), 다익스트라—을 해부하여 그리디의 우아함을 체득합니다. 마지막으로 그리디가 실패하는 경우와 이를 보완하는 **휴리스틱(Heuristic) 및 근사 알고리즘(Approximation Algorithm)**의 경계를 장악하는 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 그리디 설계 조건 (Greedy Correctness Conditions): 탐욕적 선택 속성(Greedy Choice Property), 최적 부분 구조(Optimal Substructure), 교환 논법(Exchange Argument) 증명.
• 클래식 그리디 (Classic Greedy Problems): 활동 선택(Activity Selection), 허프만 코딩(Huffman Coding), 코인 체인지(단위 동전 시스템), 분수 배낭(Fractional Knapsack), 작업 스케줄링(Job Scheduling).
• 그리디 MST/그래프 (Greedy on Graphs): 크루스칼(Kruskal) + 유니온-파인드(Union-Find), 프림(Prim) + Min-Heap.
• 근사 알고리즘 (Approximation Algorithms): 2-근사 알고리즘(2-Approximation), 그리디 휴리스틱의 품질 보증.

Out-of-Scope

• 메타휴리스틱 (Metaheuristics): 시뮬레이티드 어닐링(Simulated Annealing), 유전 알고리즘(Genetic Algorithm) $\rightarrow$ AI/Optimization 영역.
• 정수 선형 프로그래밍(ILP): LP Relaxation 기반 근사 $\rightarrow$ Operations Research 영역.

Boundaries

• Greedy vs DP: 그리디는 "현재 선택이 미래를 보장"(탐욕적 선택 속성)할 때만 사용합니다. "현재 선택이 미래에 미치는 영향을 고려해야" 할 때는 DP가 필요합니다. 분수 배낭(Fractional Knapsack): 가치/무게 비율로 그리디 → 최적. 0/1 배낭(0/1 Knapsack): 물건 전체를 넣거나 말아야 하므로 그리디로 최적 보장 불가 → DP 필요.

3. Counterexample

• 탐욕적 선택의 오류, 동전 문제 (Non-canonical Coin System): 동전 [1, 3, 4]로 금액 6을 만드는 최소 동전 수 문제에 그리디를 적용하면: 가장 큰 동전 4를 선택 → 나머지 2 → 1+1 → 총 3개. 하지만 최적은 3+3 = 2개입니다. 그리디가 최적해를 보장하는 건 [1, 5, 10, 25]처럼 큰 동전이 작은 동전의 배수인 "정규(Canonical)" 동전 시스템뿐입니다. 임의 동전 시스템에서는 DP가 필수입니다.
• 활동 선택에서 최장 활동 먼저 전략의 실패 (Activity Selection Greedy Failure): 활동 선택 문제에서 "가장 오래 걸리는 활동을 최대한 많이 선택하자"는 잘못된 그리디. 활동 [(1,10), (2,4), (5,6), (7,9)]에서 (1,10)을 선택하면 나머지 3개가 겹쳐 선택 불가. 올바른 그리디는 "종료 시간이 가장 빠른 활동 먼저"로 (2,4), (5,6), (7,9) 3개를 선택하는 전략입니다.

4. Prerequisites

• 정렬 (Sorting) (Basic): 대부분의 그리디는 입력을 정렬(종료 시간, 가치/무게 비율, 간선 가중치)하고 시작합니다. (04-03-01 Recursion, Sorting)
• 우선순위 큐 (Heap) (Recommended): 허프만 코딩, 프림 MST 등 그리디 알고리즘의 핵심 자료구조. (04-02-02 Heaps)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 탐욕의 수학적 조건과 교환 논법, 그리디 정당성 증명 (Greedy Correctness)

• Why to Learn: "이 문제에 그리디를 써도 되나?"라는 핵심 질문에 "탐욕적 선택 속성이 성립하면 된다"는 수학적 답변을 교환 논법(Exchange Argument)으로 증명하는 역량을 갖추기 위함입니다.
• What to Learn:
  • Concepts: 탐욕적 선택 속성(Greedy Choice Property), 최적 부분 구조(Optimal Substructure), 교환 논법(Exchange Argument by Contradiction).
  • Skills: 귀납법으로 그리디의 정확성 증명, 반례(Counterexample)로 그리디 실패 입증.
• How to Learn:
  • 1단계: 교환 논법: 최적해 OPT에서 그리디가 선택한 원소(가장 빠른 종료 활동 a*)를 포함하지 않는다 가정. OPT의 첫 번째 원소를 a로 교환해도 활동 수가 줄지 않음(a의 종료가 빠르므로 이후 원소들에 간섭 없음) → OPT도 a*를 포함하는 해로 변환 가능 → 그리디 선택이 최적해를 포기하지 않음(탐욕 선택 속성 증명)을 해부합니다.
  • 2단계: 탐욕 선택 속성이 없는 0/1 배낭에 그리디를 적용하면 반례가 존재함을 구체적 숫자로 보여주는 역방향 증명을 뜯어봅니다.
• Implement: activity_selection_greedy(activities) 파이썬 구현. activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)] → 종료 시간 정렬 후 그리디 선택 [(1,4),(5,7),(8,11),(12,16)] 4개 출력. 그리디 vs Brute Force 결과 비교 검증.

Recommended

Core Topic 02: 빈도에 따른 최적 코드, 허프만 코딩 (Huffman Coding)

• Why to Learn: ZIP, gzip, JPEG의 무손실 압축 알고리즘의 심장인 허프만 코딩이 "자주 등장하는 문자에 짧은 비트코드, 드물게 등장하는 문자에 긴 비트코드"를 자동으로 할당하는 그리디의 완벽한 응용임을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 가변 길이 코드(Variable-Length Code), 접두사 코드(Prefix-Free Code), 허프만 트리(Huffman Tree), Min-Heap 기반 구축.
  • Skills: 허프만 트리에서 비트 코드 추출, 압축률(Compression Ratio) 계산.
  • Tools: Python heapq 기반 허프만 구축.
• How to Learn:
  • 1단계: 문자 빈도 {A:5, B:9, C:12, D:13, E:16, F:45}. Min-Heap에 모든 문자를 빈도 키로 삽입. Pop 두 개, 빈도 합산해 새 내부 노드로 만들어 Heap에 Push 반복. 최종 트리에서 F(빈도 45)는 1비트, A(빈도 5)는 4비트를 받는 허프만 구축 역학을 해부합니다.
  • 2단계: 최종 트리에서 루트부터 DFS: 왼쪽 = 0, 오른쪽 = 1로 각 리프(문자)의 비트 코드를 추출. 모든 코드가 서로의 접두사가 아닌 Prefix-Free 조건 만족을 증명합니다.
• Implement: 파이썬 huffman_encoding(freq_dict). freq = {'A':5,'B':9,'C':12,'D':13,'E':16,'F':45} → 각 문자의 코드 {'F':'0','C':'100','D':'101','B':'110','E':'1110','A':'1111'} 출력. 평균 코드 길이(Σ freq[c]*len(code[c]) / Σ freq[c])를 고정 길이 3비트와 비교하여 압축 효율 수치 증명.

Practical

Core Topic 03: 사이클 없는 최소 간선의 집합, MST 알고리즘 (Kruskal & Prim MST)

• Why to Learn: 도시 간 최소 비용 전력망 설계, 네트워크 토폴로지 최적화, 클러스터링 알고리즘의 핵심인 최소 신장 트리(MST)를 그리디로 구하는 크루스칼과 프림 두 알고리즘의 동작과 적합한 그래프 유형을 장악하기 위함입니다.
• What to Learn:
  • Concepts: 최소 신장 트리(Minimum Spanning Tree, MST), 크루스칼(Kruskal, 간선 정렬+사이클 방지), 프림(Prim, 현재 트리에서 최소 간선 확장), 유니온-파인드(Union-Find, Disjoint Set Union).
  • Skills: 유니온-파인드 경로 압축(Path Compression) + 랭크(Rank) 최적화.
  • Trade-offs: 크루스칼은 O(E log E) 간선 정렬이 병목으로 희소 그래프(Sparse Graph, E≈V)에 유리합니다. 프림은 Min-Heap으로 O(E log V)이며 밀집 그래프(Dense Graph, E≈V²)에 유리합니다.
• How to Learn:
  • 1단계: 크루스칼: 모든 간선을 가중치로 정렬. 가장 가벼운 간선부터 선택하되, 두 정점이 이미 같은 컴포넌트(Union-Find로 확인)면 사이클 형성이므로 건너뜀. V-1개 간선 선택 시 MST 완성을 해부합니다.
  • 2단계: 프림: 임의 정점에서 시작, 현재 트리와 연결된 미방문 정점으로의 최소 가중치 간선을 Min-Heap에서 Pop. 선택된 간선을 MST에 추가, 새 정점의 모든 인접 간선을 Push하는 확장 역학을 뜯어봅니다.
• Implement: 파이썬 kruskal_mst(edges, n) + prim_mst(adj, n). 7개 정점 그래프에서 두 알고리즘 결과 MST 총 가중치 동일함을 assert. Union-Find find(x) 경로 압축, union(x,y) 랭크 기반 최적화 구현 후 대규모 그래프(1000 정점)에서의 성능 측정.

Advanced

Core Topic 04: 불가능한 문제의 괜찮은 답, 근사 알고리즘 (Approximation Algorithms)

• Why to Learn: NP-하드(NP-Hard) 문제들(여행하는 외판원 TSP, 집합 덮기 Set Cover)은 정확한 최적해를 다항 시간에 구할 수 없지만, 그리디 휴리스틱으로 **"최적의 2배 이내"를 보장하는 2-근사 해(2-Approximation)**를 구해 실무에서 활용하는 이론과 실제를 꿰기 위해서입니다.
• What to Learn:
  • Concepts: 근사율(Approximation Ratio, ρ), 2-근사 MST 기반 TSP, H(n)-근사 Set Cover(조화 급수), Vertex Cover 2-근사.
  • Skills: 근사 알고리즘 품질 하한 증명, 랜덤화 근사(Randomized Approximation).
• How to Learn:
  • 1단계: Set Cover 그리디 H(n)-근사: 각 단계에서 덮지 않은 원소를 가장 많이 포함하는 집합을 선택. 이 그리디의 근사율이 H(n) = ln n + 1임을 수학적으로 증명(최적 k개 집합 대비 그리디가 최대 k * ln n개 집합 사용)하는 역학을 해부합니다.
  • 2단계: MST 기반 TSP 2-근사: (1) MST 구축 → (2) MST를 Pre-order DFS로 방문(Eulerian Walk) → (3) 이미 방문한 정점 Skip하여 Hamilton Circuit 구성. MST 가중치가 OPT 하한이므로 이 해가 OPT × 2 이내임을 삼각 부등식으로 증명합니다.
• Implement: 파이썬 set_cover_greedy(universe, subsets). 100개 원소, 20개 부분집합에서 그리디 Set Cover 수행. 실제 최적해(Brute Force, 소규모)와 비교하여 그리디 해가 H(100) ≈ 5.6배 이내임을 수치 증명. nearest_neighbor_tsp(cities) 구현으로 TSP 근사 투어 시각화(좌표 그래프).

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Greedy) — Efficiency patterns.
• [P1] CS2023 - AL/Algorithms and Complexity (Greedy Algorithms) — Core requirements.

Secondary

• [Artificial Intelligence: A Modern Approach] Russell — Heuristic search depth.
• [The Algorithm Design Manual] Steven Skiena — Greedy and heuristic cases.

Industry

• [Google Maps: Route Planning Heuristics] — Real-world A* application.
• [NVIDIA: Parallel Pruning for Pathfinding] — Hardware-accelerated search.

9. Final Checklist

Primary

• '탐욕적 선택'을 한 결과가 왜 미래의 선택 가능성을 물리적으로 해치지 않아야 하는지 그 '독립성'을 설명 가능한가? (P1)
• 프림이나 크루스칼 알고리즘을 사용해 네트워크의 '최소 건설 비용'을 수리적으로 도출할 수 있는 가? (P1)

Secondary

• 탐욕 기법이 '전역 최적해'를 보장하지 못하는 케이스를 '0/1 배낭 문제' 등의 사례를 들어 물리적 근거로 소통 가능한가?
• A* 알고리즘에서 $f(n) = g(n) + h(n)$ 수식이 왜 '경험'과 '현실'의 결합인지 도출할 수 있는 가?

Industry

• 게임 엔진 내비게이션 메쉬(NavMesh) 설계 시, 매 순간의 연산량을 줄이기 위한 '계층적 휴리스틱'을 제안할 수 있는 가? (SFIA)
• 물류 배송 시나리오에서 TSP 난제를 해결하기 위해 근사 알고리즘이 내놓은 '비용 상한선'의 물리적 신뢰도를 기술할 수 있는 가?