탐욕 알고리즘 (Greedy Algorithm)

 

1. 정의

매 순간 최선처럼 보이는 선택을 하는 방식

즉, 현재 단계에서 가장 좋아보이는 선택을 반복해서 전체 해답을 만들어가는 방식

 

하지만 각 단계에서의 최선 선택이 전체적으로 최선이라는 보장은 없기 때문에 항상 정답을 보장하는 것은 아니고 적절한 조건을 만족할 때만 올바른 해를 준다

---

2. 핵심 4가지 함수

1. 타당성 함수 : 지금까지 고른 후보들이 문제 조건을 만족하는지를 확인하는 함수

2. 선택 함수 : 아직 사용하지 않은 후보들 중에서 가장 좋아보이는 것을 선택하는 함수

3. 해답 점검 함수 : 지금까지 고른 것들이 완전한 해답인지 검사하는 함수

4. 목적 함수 : 지금 선택한 해가 얼마나 좋은지 점수(가치)를 매기는 함수 

---

3. 절차

1. S = ∅ (아무것도 선택하지 않은 상태로 시작)

2. 가장 좋아보이는 후보 하나를 선택한다

3. 그걸 선택해도 조건을 만족하는지 확인한다

4. 조건을 만족하면 해당 집합에 추가한다

5. 현재까지 고른 것들이 문제를 해결했는 지 확인한다

6. 2-5까지의 과정을 문제가 해결될 때 까지 반복한다

---

4. 예시

4.1. 거스름돈 문제

동전 종류가 500, 100, 50, 10원이 있을 때, 760원을 가장 적은 수의 동전으로 거슬러 주는 문제

→ 항상 가장 큰 동전부터 선택

 

4.2. 최소 신장 트리 (Minimum Spanning Tree, MST)

항상 가장 짧은 간선을 선택해 나가면서 최소 트리를 만든다