10. 탐욕 알고리즘

#1. 탐욕 알고리즘
* 최적의 해에 가까운 값을 구하기 위해 사용
* 그사치 추정에 활용
* 반드시 최적의 해를 구할 수 있는 것은 아님
* 여러 경우 중 하나를 결정해야 할때 마다 매 순간 최적이라고 생각되는 경우를 선택하는 방식

#2. 탐욕 알고리즘의 예
지불해야 할 값이 4720원일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 작게 지불하는 방법
* 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현
* 매 순간 최적이라고 생각되는 경우를 선택하면 됨

coin_list = [1, 100, 50, 500]
print(coin_list)
coin_list.sort(reverse=True)
print(coin_list)
-->
[1, 100, 50, 500]
[500, 100, 50, 1]

#모범 답안
coin_list = [1, 100, 50, 500]

def min_coin_count(value, coin_list):
  total_coin_count = 0
  details = list()
  coin_list.sort(reverse=True)
  for coin in coin_list:
    coin_num = value // coin
    total_coin_count += coin_num
    value -= coin_num * coin
    details.append([coin, coin_num])
  return total_coin_count, details

min_coin_count(4720, coin_list)
-->

(31, [[500, 9], [100, 2], [50, 0], [1, 20]])


### 발표 과제
* 최단 경로 알고리즘(다익스트라 알고리즘) #개념 예제로 발표
* 최소 신장 트리
* 백 트래킹