[알고리즘] 탐욕적 알고리즘 Part 1 - Basic

* 탐욕적 알고리즘
 - 현재 상태에서 가장 최적인 상태를 선택하는데 사용하는 알고리즘
 - 상태가 변할 때 마다 새로운 실행을 하여서 최적의 상태를 찾는다.

ex) 문구점에 627원 짜리 물건을 사는데 1,000 원을 냈다.
      가게 주인은 500, 100, 50, 10, 5, 1짜리 동전을 이용해서 최고 적은 수의 동전으로 거스려주로고 한다.
      최소의 동전의 수는 몇개인가?
 
 > 거스름돈 : 373원
 > 탐욕적 알고리즘은 가장 좋아 보이는 것부터 선택을 실시한다.
 ① 500원 짜리 동전을 선택한다.
     373 < 500 -> 500 원짜리를 내려 놓는다.
 ② 100원 짜리 동전을 선택한다.
     373 > 100 -> 100원짜리 동전을 가진다. / 남은 금액 : 273원
 ③ 100원 짜리 동전을 다시 선택한다.
     273 > 100 -> 100원짜리 동전을 가진다. / 남은 금액 : 173원
 ④ 100원 짜리 동전을 다시 선택한다.
     173 > 100 -> 100원짜리 동전을 가진다. / 남은 금액 : 73원
 ⑤ 100원 짜리 동전을 다시 선택한다.
     73 < 100 -> 100원짜리를 내려 놓는다.
 ⑥ 50원 짜리 동전을 선택한다.
     73 > 50 -> 50원짜리 동전을 가진다. / 남은 금액 : 23원
 ⑦ 50원 짜리 동전을 다시 선택한다.
     23 < 50 -> 50원짜리를 내려 놓는다. 
 ⑧ 10원 짜리 동전을 선택한다.
     23 > 10 -> 10원짜리 동전을 가진다. / 남은금액 : 13원
 ⑨ 10원 짜리 동전을 다시 선택한다.
     13 > 10 -> 10원짜리 동전을 가진다. / 남은 금액 : 3원
 ⑩ 10원 짜리 동전을 다시 선택한다.
     3 < 10 -> 10원짜리를 내려 놓는다.
 ⑪ 5원 짜리 동전을 선택한다.
     3 < 5 -> 5원짜리를 내려 놓는다.
 ⑫ 1원 짜리 동전을 선택한다.
     3 > 1 -> 1원짜리 동전을 가진다 . / 남은 금액 : 2원
 ⑬ 1원 짜리 동전을 다시 선택한다.
     2 > 1 -> 1원짜리 동전을 가진다. / 남은 금액 : 1원
 ⑭ 1원 짜리 동전을 다시 선택한다.
     1 = 1 -> 1원짜리 동전을 가진다. / 남은 금액 : 0원
 ⑮ 나에게 가지고 있던 9개의 동전을 돌려준다. 

 > 만약, 위 문제에서 12원짜리 동전이 존재한다가 생각해보자.
    그럴 경우 이 알고리즘(탐욕적 알고리즘)을 통해서 최소의 동전 개수를 구할수 없게 된다. 

* 탐욕적 알고리즘의 개요(풀이법)
 ⓐ 비어 있는 해답모음으로 시작한다.
 ⓑ 탐욕적 기준에 따라서 해답 모음에 추가할 항목을 선택한다.
 ⓒ 새 해답 모음이 적절 한지를 확인한다. 
 ⓓ 새 해답 모음이 해답이라면 끝낸다. 아니면 2번으로 돌아가서 반복한다.

 > 위의 예에 풀이법을 적용하면
 ⓐ 비어있는 해답 모음이란 아무것도 동전을 선택하지 않았을 경우이다.
 ⓑ 탐욕적 기준은 큰 금액의 동전을 선택하는 것으로 500월 100원 50원... 순으로 선택을 하게 될 것이다.
 ⓒ 선택한 동전의 금액이 남은 금액보다 큰가의 여부를 판단하여서 적절한가를 확인한다.
 ⓓ 남은 잔금이 0이 되었는지 확인해보고 아니면 ⓑ로 돌아간다.