탐욕법(Greedy)

탐욕법은 말그대로 탐욕적으로 눈앞에 보이는 상황에서 가장 좋은 상황(최선의 선택)을 고르는 것을 말한다.

탐욕법은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다.

---

탐욕법 사용 가능 조건

1. Local minimum과 Global minimum이 같을 경우
2. sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 ( 동적계획법과 동일)
3. Problem들의 solution들이 서로 영향을 주면 안된다

---

탐욕법 예제

탐욕법의 가장 대표적인 예시는 coin change이다

 

예를 들어 760원을 [10,50,100,500]의 동전으로 주는데 동전을 최소로 주는 방법을 구하는 것이다. 이 때는 가장 큰 500원 부터 차례대로 채워가면 정답이 나온다.

 

500 X 1 = 500 → 260

100 X 2 = 200 → 60

50 X 1 = 50 → 10

10 X 1 = 10 → 0

 

총 4개의 동전

 

>Greedy 관련 문제 보기