그리디 알고리즘(욕심쟁이 알고리즘):
매 선택에서 가장 최적의 선택을 하여 적절한 답을 찾아가는 설계 기법. 작은 쪽이 반드시 큰 쪽의 배수인 경우 적용할 수 있다.
큰 수의 약수들로 큰 수를 만들 수 있다면, 큰 액수의 동전으로 교체했을 때 항상 동전의 개수를 줄일 수 있게 된다. 만약 배수가 아니라면 그리디 알고리즘을 더이상 사용할 수 없게 된다.
예시
i) 500, 100, 50, 10, 5, 1원으로 거스름돈을 거스러주는 경우 -> 그리디 알고리즘
ii) 500, 400, 100일때 800엔의 거스름돈을 주는 경우 500, 100x3로 이뤄지만 동전 4개가 되지만, 400x2로 구성하면 동전 2개가 된다. 이 경우 그리디 알고리즘을 이용하여 500엔부터 세었을 때 최적의 값을 찾을 수 없게되므로 알고리즘을 사용할 수 없다.(다이나믹 알고리즘을 사용해야한다.)
java