[알고리즘] [12] 탐욕 알고리즘

1. 탐욕 (Greedy) 알고리즘

• 최적 해를 구하는 근시안적 방법이다.
• 최적화 문제 (optimization) : 가능한 해들 중 가장 좋은 해를 찾는 문제
• 여러 경우 중 하나를 택할 때마다 그 순간의 최적을 선택해 나가며 해답을 찾는 방식이다.
• 지역적으로는 최적이지만 최종 답이 최적이라는 보장은 없다.

2. 배낭 짐싸기 (Knapsack)

• 최대 무게를 넘지 않으며 가장 큰 값어치를 얻어야 하는 문제
• 0 -1 Knapsack : 물건을 쪼개지 않고 통째로 담아야 하는 문제
• Fractional Knapsack : 물건을 쪼개어 부분적으로 담을 수 있는 문제

0 - 1 Knapsack 완전 검색

• 가능한 모든 부분집합 중 최대 무게를 넘지 않는 경우에 대해 값어치를 구한다.
• 크기가 n인 부분집합의 수는 2ª이므로 시간 복잡도가 지수적으로 증가한다.

0 - 1 Knapsack 탐욕적 방법

• 값이 비싼 물건 또는 무게가 가벼운 물건 또는 단위 무게당 값어치가 높은 물건부터 채워나간다.
• 탐욕적 방법으로는 최적 해를 찾을 수 없다.

Fractional Knapsack 탐욕적 방법

• 물건의 일부를 잘라서 담을 수 있으므로 단위 무게 당 값어치가 높은 물건부터 채워 나간다.
• 이 경우, 탐욕적 방법으로 최적 해를 구할 수 있다.

---

3. 회의실 배정

1931번: 회의실 배정

활동 선택 문제 (Activity-selection problem)

• 시작 시간과 종료 시간이 있는  n개의 활동 중 서로 겹치지 않는 최대 개수의 활동 집합을 구하는 문제
• 탐욕 기법을 적용한다.

4. 탐욕 알고리즘의 필수 요소

• 탐욕적 선택이 최적해로 갈 수 있음을 증명해야 한다.
• 최적화 문제를 최적 부분 구조로 정형화해야 한다.
• 대표 탐욕 기법 : Prim, Kruskal, Dijkstra