Greedy Algorithm

매 순간 최선의 경우만을 골라간다 (나중은 생각하지 않는다!)

동전 거스름돈 문제

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

⇒ 금액을 큰 것부터 주면 좋다. (800 - 500 - 100 - 100 -100) Greedy 이다.

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

⇒ Greedy Algorithm이 먹히지 않는다. (400+400 = 800, 동전 두개씀)

문제가 그리디 문제인지 판별하는 것이 어렵다!

정당성 증명 (두 가지 조건 만족하면 Greedy)

1. 탐욕적 선택 속성

모든 경우를 볼 필요없이 항상 최선의 경우만 골라가면 최적해라는 것을 보인다. 탐욕적으로 선택할 때, "손해" 볼 일이 없다.

2. 최적 부분 구조

부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다. (DP 처럼)

대부분의 경우 너무 당연해서 쉽고 직관적이다.

이전에 했던 선택이 후의 선택에 영향을 끼치면 탐욕법이 성립은 안한다고 알고 있습니다.

정리

• 항상 그때그때마다 최선의 경우만 탐욕적으로 쫓는 알고리즘
• 정말 이 문제가 그리디로 풀릴지 신중히 판단하자.
  • 반례가 없을까 고민
  • 공부할 때는 문제마다 증명해봐야 도움이 된다.
  • 실전에서는 시간이 부족할테니 엄밀한 증명은 힘듦