알고리즘
Greedy
다른 이름: Greedy Algorithm , 탐욕 알고리즘
정의
탐욕 알고리즘. 매 순간 최선의 선택(지역 최적)을 반복. 전역 최적해 보장 불가(반례 확인 필수). 활동 선택, 동전 교환(특정 조건), 최소 신장 트리(Kruskal, Prim). 정렬 + 그리디 패턴 흔함. DP 대비 빠르나 증명 필요
상세 설명
기술 스펙
- 탐욕 선택 속성: 지역 최적 선택이 전역 최적에 포함
- 최적 부분 구조: 선택 후 남은 문제도 최적
- 시간복잡도: 대부분 O(n log n) - 정렬 포함
- 증명 필요: 교환 논법(Exchange Argument)
- 반례 찾기: 0-1 배낭, 임의 동전 최소 개수
실무 활용
- 활동 선택: 종료 시간 빠른 순 선택
- 동전 교환: 큰 단위부터 (특정 화폐 체계만)
- 최소 신장 트리: Kruskal, Prim
- Huffman 코딩: 빈도 기반 압축
- 백준: 11047 (동전 0), 1931 (회의실 배정)
장점
- 매우 빠름: 정렬 O(n log n) + 선택 O(n)
- 구현 간단: 정렬 후 반복문
- DP 대비 효율: 상태 저장 불필요
- 직관적: 최선 선택 반복
단점 및 제약
- 최적해 불보장: 반례 확인 필수
- 증명 어려움: 교환 논법 수학적
- DP와 혼동: 0-1 배낭은 DP
- 정렬 필수: 대부분 O(n log n) 추가
호환성
C++ STL sort, Python sorted, Java Arrays.sort
표준 정보
표준화 기구: 알고리즘 교과서 표준. Dijkstra, Kruskal, Prim
출시 연도: 1970년