Greedy Algorithm 그리디 with Kotlin

Greedy Alogrithm
최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘으로 여러 경우 중 하나를 결정해야할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종적인 값을 구하는 방식을 말함

대표적인 알고리즘으로는 " 거스름돈" 문제가 있다
물건을 구매할 때 지폐를 사용해서 금액에 맞게 지불한다. 금액이 주어지면 내야하는 지폐 개수의 최솟값을 구하는 문제이다.

성립 조건

1. 탐욕스러운 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는 조건

2. 최적 부분 구조 조건 : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결방법이다라는 조건이 성립되어야 잘 작동한다.