15.5 요약
1. 핵심 정리
- 탐욕 알고리즘은 주로 최적화 문제에 사용하며, 매 결정 단계에서 국소 최적 선택을 내려 전역 최적해를 얻으려는 원리다.
- 탐욕 알고리즘은 선택을 하나씩 반복하며 매번 문제를 더 작은 부분 문제로 바꾸고, 해결될 때까지 진행한다.
- 탐욕 알고리즘은 구현이 간단하고 풀이 효율이 높다. 시간 복잡도는 보통 동적 계획법보다 낮다.
- 동전 교환에서는 일부 동전 조합에 대해 최적해를 보장하지만, 다른 조합에서는 매우 나쁜 해를 찾을 수도 있다.
- 탐욕 알고리즘에 적합한 문제는 탐욕적 선택 속성과 최적 부분 구조를 가진다. 탐욕적 선택 속성은 전략의 유효성을 나타낸다.
- 복잡한 문제에서는 탐욕적 선택 속성의 증명이 쉽지 않다. 동전 교환처럼 반례로 부정하는 편이 상대적으로 쉬운 경우가 있다.
- 탐욕 문제의 풀이는 문제 분석, 탐욕 전략 결정, 정확성 증명의 세 단계로 나뉜다. 전략 결정이 핵심이며, 정확성 증명이 어려운 경우가 많다.
- 분할 가능한 배낭은 0-1 배낭에서 물건의 일부를 고를 수 있도록 바꾼 문제이므로 탐욕 알고리즘으로 풀 수 있다. 전략의 정확성은 귀류법으로 증명할 수 있다.
- 최대 용량 문제는 모든 경우를 열거하면 시간 복잡도가 \(O(n^2)\)이다. 매번 낮은 칸막이를 안쪽으로 옮기는 탐욕 전략으로 \(O(n)\)까지 최적화할 수 있다.
- 정수 분할의 최대 곱 문제에서는 \(\geq 4\)인 정수를 계속 나누어야 하고 최적인 인수는 \(3\)이라는 두 탐욕 전략을 차례로 도출했다. 코드에는 거듭제곱이 포함되므로 시간 복잡도는 구현 방식에 따라 보통 \(O(1)\) 또는 \(O(\log n)\)이다.