그리디 알고리즘은 DP보다 구현하기 쉽고 시간 복잡도가 우수하지만, 항상 최적의 해는 보장하지 못한다. 따라서 코딩테스트에서 적용할 때는 항상 논리 유무를 충분히 살펴야 한다.
Greedy 알고리즘, 탐욕법
핵심 이론
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. DP는 하위 문제에 대한 최적의 솔루션을 찾은 다음, 전체 최적 솔루션을 찾는 것이라면, Greedy는 각 단계마다의 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태이다.
과정
1. 해 선택
현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사
현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사
현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.
위에서 그리디 알고리즘은 루트 노드에서 3과 12중 12를 선택하고, 그 다음에 6을 선택하므로 전체에 대한 최적 솔루션은 못찾는다. 따라서 위의 문제는 이진트리로 정렬하는 등의 작업을 하지 않는 이상 Greedy로 풀 수 없다.
조건
1. 탐욕적 선택 속성 (Greedy Choice Property)
현재의 선택이 앞으로의 선택에 영향을 미치지 않고 최적해로 이어질 수 있어야 한다.
2. 최적 부분 구조 (Optimal Substructure)
부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 한다.
3. 단항 선택 조건 (Unary Choice Condition)
매 단계마다 오직 하나의 선택만 가능해야 하고, 각 단계에서 여러 선택지가 있는 경우 그중 하나를 선택하면 이후 단계에 영향을 미치지 않아야 한다.
위 3가지 조건을 만족시키면, Greedy 알고리즘은 최적해를 보장한다.
예제
https://www.acmicpc.net/problem/11047
1. 문제 분석하기
위에서는 그리디 알고리즘으로 풀 수 있도록 뒤의 동전 가격이 앞에 나오는 동전 가격의 배수가 된다는 조건을 부여했다. 즉, 동전을 최소로 사용하여 목표 금액을 달성하기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.
2. 손으로 풀어보기
- 가격이 큰 동전부터 내림차순으로 목표금액보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
- 탐색을 멈춘 동전의 가격으로 목표금액을 나눠 몫은 동전 개수에 더하고, 나머지는 목표금액으로 갱신한다.
- 과정 1-2를 나머지가 0이 될 때까지 반복한다.
