- 탐욕 알고리즘은 최적 해를 구하는데 사용되는 근시안적인 방법
- 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은 (최대 혹은 최소) 해를 찾는 문제
- 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달함
- 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없음
- 일단 한번 선택된 것은 번복하지 않고 이러한 특성 때문에 대부분의 탐욕 알고리즘은 단순하며, 제한적인 문제들에 적용됨
- 도둑이 여러개의 물건 중 배낭에 담을 수 있는 총 무게(W)를 초과하지 않으면서 가치가 최대가 되는 물건을 담는 알고리즘 구현 하기
- 해당 문제는 배낭이 수용가능한 총 무게 W를 만족하면서 최대 가치가 되는 부분집합을 찾는 문제
- Knapsack은 두가지 문제 유형이 존재
- 0-1 Knapsack : 배낭에 물건을 통째로 담아야 하는 문제, 물건을 쪼갤 수 없는 경우
- Fractional Knapsack : 물건을 부분적으로 담는 것이 허용되는 문제, 물건을 쪼갤 수 있는 경우
- 탐욕적 선택은 최적해로 갈 수 있음을 보여라
- 즉, 탐욕적 선택은 항상 안전
- 최적화 문제를 정형화
- 하나의 선택을 하면 풀어야 할 하나이 하위 문제가 남음
| 알고리즘 | 목적 | 설명 | 유형 |
|---|---|---|---|
| Prim | N개의 노드에 대한 최소 신장 트리(MST)를 찾음 | 서브트리를 확장하면서 MST를 찾음 | 그래프 |
| Kruskal | N개의 노드에 대한 최소 신장 트리(MST)를 찾음 | 싸이클이 없는 서브 그래프를 확장하면서 MST를 찾음 | 그래프 |
| Dijkstra | 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾음 | 주어진 정점에서 가장 가까운 정점을 찾고 그 다음을 정점을 반복해서 찾음 | 그래프 |