2021-06-11
지금 상황에서 가장 좋은 것만 고르는 방법으로, 현재의 선택이 나중에 미칠 영향에 대해서는 전혀 고려하지 않는다.
코딩 테스트에서 출제되는 그리디 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올리는 능력을 요구한다.
문제를 보고 현재 상황에서 가장 좋아보이는 것만 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다.
그리디 알고리즘 문제는 기준에 따라 가장 좋은 것을 선택하는 방법이므로, 문제에서 '가장 큰 순서대로' 와 같은 기준을 은근히 제시해준다. 따라서 정렬 알고리즘과 짝을 이뤄 출제되기도 한다.
어떤 문제를 보고 해결 방법이 떠오르지 않는다면 탐욕적인 방법을 생각해보자. 그래도 해결 방법이 떠오르지 않는다면, 책에서 나중에 배울 다이나믹 프로그래밍, 그래프 이론 등을 고민해보는 것도 방법이 될 수 있다.
-
문제) 거스름돈
카운터에서 손님에게 N원을 거슬러줘야 할 때 필요한 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈은 항상 10의 배수이고, 500원, 100원, 50원, 10원짜리 동전들만을 무한히 사용해서 거슬러줄 수 있다.
-
해설
그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로, '가장 큰 화폐 단위부터 최대한' 거슬러 준다는 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.
- step0) N = 1260원
- step1) 500원으로 거슬러줄 수 있는 가장 큰 돈은 1,000원, 즉 500원 2개 -> 남은 돈 N = 260원
- step2) 100원으로 거슬러 줄 수 있는 가장 큰 돈 200원, 100원 2개 -> 남은 돈 N = 60원
- step3) 50원 1개 -> N = 10원
- step4) 10원 1개 -> N = 0원
- 정답) 동전의 최소 개수는 6개
-
코드
n = 1260
count = 0
# 단위가 큰 동전부터 차례대로 확인
list = [500, 100, 50, 10]
for coin in list:
count += n // coin # 해당 단위로 거슬러 줄 수 있는 최대 동전 개수
n %= coin
print(count)-
시간복잡도
화폐의 종류를 K라 할 때, 코드의 시간복잡도는 O(K)이다.
거슬러 줘야할 돈 N이 보이지 않는데, 이 알고리즘의 시간복잡도는 동전의 종류에만 영향을 받고 거슬러 줄 금액 크기와는 무관한 것을 알 수 있다.
