거스름돈

[알고리즘]그리디(Greedy, 탐욕법, 욕심쟁이기법)

그리디 알고리즘이란? 탐욕알고리즘, 욕심쟁이기법 이라고도 합니다. 매순간 최적이라고 생각하는 해를 선택해나가서 최종적으로 최적해에 도달하는 알고리즘이라고 할 수 있습니다. 그렇게 때문에 구한 해가 항상 최적임이 보장되지는 않아서 근삿값을 구하는 용도로 사용되기도 합니다. 탐욕법이 충족되기 위한 조건 앞의 선택이 이후의 선택에 영향을 주지않을 때 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해일때 이렇게 2가지 조건을 만족할 때 그리디알고리즘이 잘 작용합니다. 이 조건들을 만족하지 못하면 최적해를 구하지 못하고 근삿값은 구할 수 있습니다. 개념자체만 봤을 때는 이해가 잘 안될 수 있으니 예제를 봅시다. 예제1 - 거스름돈(백준 5585번) 잔돈으로 500, 100, 50, 10, 5, 1엔이 있고 1..