0. 탐욕 알고리즘이란?
탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.
일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
각 선택 시점에서 이루어지는 결정은 그 순간에는 최적이지만, 그 선택이 모인 최종적인 해답이 최적이라는 보장은 없다.
1. 배낭 짐싸기(Knapsack)
배낭에 담을 수 있는 물건의 총 무게(W)가 정해져 있다.
이 때, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건을 담는 경우, 그리디 알고리즘을 생각해볼 수 있다.
1-1. 0-1 Knapsak
배낭에 물건을 통째로 담아야 하는 문제 ➡ 물건을 쪼갤 수 없는 경우
이 방식은 그리디 알고리즘을 적용하기 어렵다.
아래에는 총무게가 30kg인 배낭에 0-1Knapsak 방식으로 그리디하게 물건을 고르는 예시들이다.
1-1-1. 값이 비싼 물건부터 담는 경우
| 무게 | 값 | |
| 물건 1 | 25kg | 10만원 |
| 물건 2 | 10kg | 9만원 |
| 물건 3 | 10kg | 5만원 |
- 그리디 알고리즘
- 물건 1 ➡ 25kg, 10만원
- 최적해
- 물건2, 물건 3 ➡ 20kg, 14만원
1-1-2. 무게가 가벼운 물건부터 담는 경우
| 무게 | 값 | |
| 물건 1 | 25kg | 15만원 |
| 물건 2 | 10kg | 9만원 |
| 물건 3 | 10kg | 5만원 |
- 그리디 알고리즘
- 물건 2, 물건 3 ➡ 20kg, 14만원
- 최적해
- 물건1 ➡ 25kg, 15만원
1-1-3. 무게 당 값이 높은 물건부터 담는 경우
| 무게 | 값 | 값/kg | |
| 물건 1 | 5kg | 50만원 | 10만원/kg |
| 물건 2 | 10kg | 60만원 | 6만원/kg |
| 물건 3 | 20kg | 140만원 | 7만원/kg |
- 그리디 알고리즘
- 물건 1, 물건 3 ➡ 25kg, 190만원
- 최적해
- 물건 2, 물건 3 ➡ 30kg, 200만원
1-2. Fractional Knapsack
물건을 부분적으로 담는 것이 허용되는 문제 ➡ 물건을 쪼갤 수 있는 경우
이 방식은 그리디 알고리즘을 적용할 수 있다.
| 무게 | 값 | 값/kg | |
| 물건 1 | 5kg | 50만원 | 10만원/kg |
| 물건 2 | 10kg | 60만원 | 6만원/kg |
| 물건 3 | 20kg | 140만원 | 7만원/kg |
- 그리디 알고리즘
- 물건 1 5kg + 물건 3 20kg + 물건 2 5kg ➡ 30kg 220만원
2. 탐욕 알고리즘 적용 문제
https://www.acmicpc.net/problem/5585
https://www.acmicpc.net/problem/1931
3. 대표적인 탐욕 기법의 알고리즘
| 알고리즘 | 목적 | 설명 | 유형 |
| Prim | N개의 노드에 대한 최소 신장 트리(MST)를 찾는다. | 서브트리를 확장하면서 MST를 찾는다. | 그래프 |
| Kruskal | 싸이클이 없는 서브 그래프를 확장하면서 MST를 찾는다. | 그래프 | |
| Dijkstra | 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다. | 주어진 정점에서 가장 가까운 정점을 찾고, 그 다음 정점을 반복해서 찾는다. |
그래프 |
반응형