[Greedy Algorithm] coin change

이 탐욕 알고리즘으로 거스름돈 교환 문제를 풀게 된다면, 큰 단위의 동전이 작은 단위의 동전의 배수가 되어야 탐욕 알고리즘을 적용할 수 있습니다. 위 같은 경우는, 10원 동전은 1과 5의 배수이고, 5는 1의 배수이므로 탐욕 알고리즘을 적용할 수 있었던 것입니다. 유의하셔야 할 점은 매 순간마다 최선의 선택을 하여 나온 해가 반드시 전체적인 최적해는 아니라는 것입니다. 그렇기 때문에, 탐욕 알고리즘을 사용할 때에는 전체적인 최적해 인지를 항상 염두해 두실 필요가 있습니다. 즉, 탐욕 알고리즘을 사용하시기 전에 탐욕 알고리즘을 사용해도 되는지 검증 단계를 거치시는게 좋습니다.

greedy 알고리즘을 사용하면 좋은 경우

 

1. 최적 부분 구조 (Optimal Substructure)

- 부분 문제를 최적화하는 것이 곧 전체를 최적화하는 것이다. 

 

2. 탐욕적 선택 속성 (Greedy Choice property)

- 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택

 

가장 대표적인 문제 최대한 적은 동전을 사용해서 돈 거슬러 주기.

단 동전은 500, 100, 50, 10원만 있다고 가정한다.

작은 동전으로 큰 동전을 만들 수 없으면 문제는 달라짐

 

why?

- 100원, 70원, 10원짜리 동전이 있다고 가정

- 140원을 거슬러 준다. 

- greedy하게 선택하면 100원 1개, 10원 4개를 선택

- 하지만 70원 2개를 선택하는 게 가장 최적임

 

 

CoinChangeProblem.pdf