탐욕법 (greedy)

• 매 순간마다 최선의 경우만 골라간다
• 다른 경우는 고려하지 않는다. 나중은 생각하지 않는다.

탐욕법 vs 완전탐색

• 모든 경우를 다 보지 않으니 완전탐색보다 빠르다
• 어떤 경우가 최선인지 찾는 게 포인트
• 규칙성도 찾아야 하기도 함

동전 거스름돈 문제

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

• 100, 400, 500원 동전들을 무한하게 갖고 있다.
• 손님에게 800원을 거슬러주려고 할 때 동전을 최소한으로 주는 방법은?
  

다만 이 문제는 그리디로 풀수 없다. 이유는?

10, 50, 100, 500원 같은 경우는 서로 배수 관계를 가지고 있다.

그래서 500원 동전을 쓸 경우 제일 이득이다.

반면 100, 400, 500원 같은 경우 400 ~ 500원 사이에서 배수 관계가 끊어진다.

800원이나 1200원을 거스를 경우 400을 우선으로 거슬러 줘야 하기 때문에 최고인 500원을 쓰는 것이 성립하지 않기 때문에 이문제는 그리디를 적용할수가 없었다.

결론

그리디 문제의 어려운 부분은 이 문제가 그리디 문제인지 판별하기가 어렵다.
문제가 진짜 그리디일까? 반례가 있지 않을까?