그리디
그리디, 당장 좋은 것만 선택하는 알고리즘이다.
Greedy의 뜻 탐욕법, 욕심쟁이 알고리즘 등 다양하게 불리는데 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 뜻한다.
그리디 알고리즘은 기준에 따라 좋은 지 안좋은지 판단해야 하기 때문에 '가장 큰 순서대로' , '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다고 한다.
이런건 정렬과 관련이 있으므로 정렬과 자주 등장한다고 함.
예제
유명한 예제는 거스름돈 예제가 있다.
거스름돈으로 500원 100원 50원 10원으로 거슬러 줄 때 거슬러 줘야 할 동전의 최소 개수를 구하는 문제가 대표적이다.
대표적인 그리디 문제로 가장 큰 화폐단위부터 거슬러준다.는 생각만으로 간단하게 풀 수 있다.
이때 그리디 알고리즘의 정당성 중 하나는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수라는 것이다. 화폐 단위가 500원 400원 100원인 경우에는 그리디 알고리즘 800원을 거슬러 준다면 500 + 100 + 100 + 100 이지만
최적의 해는 400+ 400 이 된다. 이 경우엔 그리디 알고리즘으로 푸는 것이 틀릴 수 있다.
"거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로, 항상 최적의 해를 보장할 수 있겠구나!까지 떠올릴 수 있어야 한다. "
