[알고리즘] 3. 탐욕법

1. 탐욕법 특징

• 매 순간마다 최선의 경우만을 골라간다
• 다른 경우는 고려 X, 나중은 생각 X (이것때문에 답이 아닐 수도 있다.)
• 모든 경우를 다 보지 않으니 완전탐색보다 빠르다.
• 어떤 경우가 최선인지 찾는 게 포인트
• 규칙성을 찾아야하는 상황도 있다.
• greedy로 문제인지 판별하기 정말 어렵다. (반례가 있을 수 있다....)

예제

동전 거스름돈 문제

1. 10, 50, 100, 500원 동전들을 무한하게 갖는다.
   손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법을 찾아라.

• 큰 단위의 동전부터 준다.

2. 100, 400, 5000원 동전들을 무한하게 갖는다.
   손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법을 찾아라.

• 큰 단위의 동전부터 준다. <-- greedy로 접근시 틀린다.
• why? 동전들의 배수관계가 서로 이어지지 않는다. <-- greedy로 접근 불가한 단서.