[Greedy Algorithm] 최소 동전으로 거슬러 주기

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0

    # coin_list의 값들을 큰 순서대로 본다
    for coin in sorted(coin_list, reverse=True):
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
        count += (value // coin)

        # 잔액을 계산한다
        value %= coin

    return count

# 테스트 코드
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

 
해결과정
먼저 이 문제는 최적 부분 구조(Optimal Substructure)와 탐욕적 선택 속성(Greedy Choice Property)이 있기 때문에 Greedy Algorithm으로 최적의 솔루션을 구할 수 있다. 매단계에서 가능한 가장 큰 동전을 주는 방식으로 구현하면 된다.
 
sorted 함수 사용법

sorted(coin_list)               # => 오름차순
sorted(coin_list, reverse=True) # => 내림차순

처음에 이 문제를 풀었을때 그리디 알고리즘이 아닌, 부끄럽지만 완전 노가다로 풀기로 생각했다... 그래서 생각한 코드가
while(value>0)란 조건을 걸고, value > coin_list[0]일 때 value -= coin_list[0]을 해주고, value < coin_list[0]일 때 value -= coin_list[1], value < coin_list[1]일 때 value -= coin_list[2]... 이런식으로 코드를 짜봤는데, 이게 굉장히 비효율적이고 coin_list의 값이 4개가 아니라 여러개일때 정말 아찔하다는 생각을 해서 나머지로 구하는 코드로 방향을 틀었다..ㅋㅋㅋ
가끔은 이런 생각때문에 더 효율적이고 좋은 코드가 나오는게 아닐까?라는 생각을 하고 더 꾸준하게 열심히 해야겠다는 생각이 들었다.
 

출처 코드잇