해당 글은 '이것이 코딩테스트다 with 파이썬' (나동빈 지음) 책 내용을 정리한 것입니다.
그리디 알고리즘이란?
단어 그대로 번역하면 탐욕법으로 소개되는 이 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이다. 즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
거스름돈
카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한이 존재한다고 가정. 거슬러 줘야할 돈이 N원일 때 동전의 최소 개수를 구하라.(N은 항상 10의 배수)
쉬운 예제로 이 문제를 해결할 수 있는 방법은 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
- N = 1,260원 이라고 할 때
- 1,260 - (500 * 2) = 260
- 260 - (100 * 2) = 60
- 60 - (50 * 1) = 10
- 10 - (10 * 1) = 0
- 이를 통해 총 2+2+1+1 = 6개의 동전이 사용된다.
코드
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin
n %= coin
print(count)
시간 복잡도
코드를 보면 화폐 종류(K)만큼 반복하기 때문에 시간복잡도는 O(K)이다.
예외 상황
해당 문제는 화폐 단위가 큰 단위가 항상 작은 단위의 배수이기 때문에 성립한다. 만약에 거슬러야 할 돈이 800원이고 화폐 단위가 [500, 400, 100]일 때는 (400+400) 2개가 가장 최적의 해가 된다.
그래서 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
