그리디 알고리즘

<aside>

탐욕법으로 현재 상황에서 지금 당장 좋은 것만 고른 방법을 의미

</aside>

거스름 돈 문제: 돈을 거슬러 줄 때, 어떻게 거슬러 주는가 동전을 각 몇개씩 줘야 하는가

가장 큰 화폐 단위부터 거슬러 주면 된다. (일일이 모든 경우를 따질 필요가 없다.)

</aside>

최적의 해를 가지는 이유에 대해서 정당성을 분석해야 한다.
- 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

N이 1이 될 때까지: N이 1이 될때까지 1을 빼거나, K로 나누어서 1로 만들어야 한다. 최소로 가능한 경우를 이야기 해라.

나누기가 가능하다면, 나누기 부터 해서 하면 된다.(탐욕법 포인트)

</aside>

곱하기 혹은 더하기