[그리디] 거스름돈 (예제 3-1, 이것이 코딩테스트다 with 파이썬)

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형
• 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형

 

문제

 

 

풀이

# 변수 설정 : 현재 잔액, 동전 개수
n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

 

 

해석

시간 복잡도 : O(K)

 

단위가 큰 돈부터 순서대로 거슬러준다.

이때 몫을 남기는 // 연산자를 이용하여 개수를 세고,

나머지를 남기는 % 연산자를 이용하여 잔액을 업데이트 한다.

반복문을 1회 사용했기 때문에 O(K) 시간 복잡도이다.

 

그리디 알고리즘의 정당성

그리디 알고리즘의 해법은 정당성을 늘 검토해야 한다.

이 경우에는 '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업' 아이디어가 정당하기에 가능한 알고리즘이다.

어떤 문제에서 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해보자.