토픽 20 / 82

탐욕 알고리즘 (Greedy Algorithm)

각 단계에서 지역적으로 최선의 선택을 하여 전체 최적해를 구하는 알고리즘 설계 기법

목적: 빠른 해결, 근사 해, 최적화 문제

특징: 지역 최적 선택, 선택 후 되돌리기 없음, 빠름, 최적 보장 안함(경우에 따라 보장)

조건

단계: ① 선택 → ② 적합성 검사 → ③ 해 검사(완료 여부) → ④ 반복

장점: 빠름(선형~O(n log n)), 단순, 직관적

단점: 최적해 보장 안함(문제 의존적), 반례 많음, 증명 필요

최적해 보장: 동전 교환(일부 동전 시스템), Kruskal MST, Prim MST, Huffman Coding, Dijkstra

최적해 비보장: 배낭 문제(0-1 Knapsack, DP 필요), 외판원 문제(TSP)

적용사례: Kruskal/Prim MST, Dijkstra 최단 경로, Huffman Coding, 활동 선택 문제, 동전 교환

비교: 탐욕(빠름/지역/최적 불보장) vs DP(느림/중복/최적 보장) vs 분할 정복(독립/재귀)

연관: Kruskal, Dijkstra, Huffman, 최적 부분 구조, 동적 프로그래밍