[파이썬][알고리즘] 탐욕 알고리즘 복습하기

1. 문제

탐욕 알고리즘으로 가장 대표적인 거스름돈 문제 해결하기 손님에게 거스름돈으로 줄 수 있는 최소한의 동전 개수 구하기

2. 해결방법 시간복잡도

1. 탐욕 알고리즘 O(N)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 간략 설명

1. 탐욕 알고리즘

• 대게 탐욕 알고리즘 2가지 조건에 의해 잘 작동하게 된다.
  • 1. 선택 조건 (greedy choice property)
       • 앞의 선택이 뒤의 선택에 영향을 주지 않음
  • 1. 최적 조건 (optimal substructure)
       • 문제의 일부의 해결 방법이 최적의 문제 해결 방법으로 구성되어 있음

1. 선택 조건 충족
   • 큰 단위부터 계속하여도 작은 단위가 결과값에 영향을 주지 않음
2. 최적 조건 충족
   • 최소한의 동전 개수를 주기 위해서는 큰 단위부터 거슬러줘야함