[Algorithm] 탐욕 알고리즘

# 탐욕 알고리즘(greedy algorithm)
-현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘이다.
- 그리드알고리즘, 탐욕법이라고 불리기도 한다.
-최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많다.

# 탐욕 알고리즘의 접근 방법
1. 방법 고안하기: 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안한다.
2. 정당성 확인하기: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인한다.(증명 단계)

# 거스름돈문제
-거스름돈 문제는 전형적인 탐욕 알고리즘의 예시다.
-카운터에 500원, 100원, 50원, 10운짜리 동전이 무수히 많이 존재한다.
-손님에게 6480원을 거슬러 주어야할때, 동전 개수의 최솟값은?

# 거스름돈 문제의 해법
-가장 큰 화폐 단위부터 거슬러주는 것이다.
1. 500원으로 거슬러 줄수 있는 만큼 거슬러 준다.
2. 100원으로 거슬러 줄수 있는 만큼 거슬러 준다.
3. 50원으로 거슬러 줄수 있는 만큼 거슬러 준다.
4. 10원으로 거슬러 줄수 있는 만큼 거슬러 준다.

# 거스름돈 문제의 해법 정당성 분석
- 각 화폐 단위가 배수 관계에 속하기 때문이다.
예: 120원을 거슬러 주어야 할때, 80원, 60원, 10원 동전이 있다면?
- 최적의 해: 60원*2 =120원으로, 2개의 동전이 필요하다.
- 80원부터 거슬러 준다면, 총 5개의 동전이 필요할 것이다.