[Algorithm] Greedy (그리디/탐욕)

- 그리디 알고리즘은 최적화 문제에서 주로 사용된다.

- 단계별로 가장 좋아 보이는 선택을 함으로써 전체적으로 최적의 해답을 찾으려고 시도한다.

- 항상 최적의 해를 찾지는 못하지만, 많은 경우에 효율적인 근사치를 찾을 수 있다.

Q) 거스름돈을 지불해야 하는 금액이 주어졌을 때, 동전의 개수를 최소로 하려면 어떤 동전을 사용해야 할까?

- 동전의 종류가 [25, 10, 5, 1]로 주어진다고 가정한다.

A1) 아이디어

- 주어진 금액에서 동전의 개수를 최소로 하려면 가장 금액이 큰 동전부터 차례대로 남은금액에 최대한 개수를 채우면 된다.

- 상식적인 아이디어이다.

- 이를 구현하면 다음과 같다.

그리디 알고리즘

- 상식적으로 최적의 해인 것 같은데, 그리디 알고리즘이 항상 최적의 해를 찾지 못하는 이유는?

  A) 각 단계에서 최선의 선택이 전체적으로 최적의 해를 보장하지 않기 때문.

    그리디 알고리즘은 각 단계에서 국소적인 최적해를 찾지만, 이러한 선택들이 모여 전체적으로 최적해가 되지 않을 수 있다.

  EX) 금액이 40이라고 가정하고, 동전의 종류가 [25, 20, 5, 1]인 경우, 현재 그리디 알고리즘으로는 {25원:1개},{5원:3개} 총 4개의 동전이지만, 최적의 해는 {20원:2개} 총 2개의 동전이다. 즉, 경우에 따라 근사치의 해를 찾는다.