그리디 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)이다. 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.