그리디 1-1) 거스름돈

예제1) 거스름돈

문제 해설 

이 문제의 핵심은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 방법으로 해결할 수 있다.

#코드 작성
def exch(money):
    change = [500, 100, 50, 10]
    result = []
    for i in change:
        result.append(money // i)
        money = money % i 
    return result
exch(1260)

코드를 보면 화폐의 종류만큼 반복을 수행해야한다. 따라서 종류가 K개라고 할 때 위 소스코드의 시간복잡도는 O(K)이다.

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.