hello-algo/ko/docs/chapter_greedy/summary.md

요약

핵심 정리

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