국내 알고리즘 교재에서 '탐욕법'으로 소개되는 그리디 알고리즘은 나중에 미칠 영향을 고려하지 않고 당장 좋은 것만 고르는 방법이다. 진정한 상남자식 알고리즘이다.
기본 구조를 암기해야 하는 정렬 알고리즘이나 최단 경로 등과 달리, 비교적 사전 지식으로부터 자유롭다는 특성을 갖고 있다. 바꿔 말하면 그만큼 다양하게 출제될 수 있기 때문에, 많은 유형을 접해보고 공부하는 훈련이 필요하다. 창의성과 아이디어는 덤이다.
'가장 좋은 것'이라는 판단을 위해서는 기준이 주어져야 하는데, 그리디 알고리즘 유형의 문제들에서는 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 등의 기준을 알게 모르게 제시해 준다. 특히 정렬 알고리즘과 짝을 이뤄 출제된다.
예제 3-1 거스름돈
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500월, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
문제를 읽고 떠올린 pseudo formula이다. 연습문제 수준의 난이도로 코드 구현까지 간단하게 해결했다. 아래 코드는 수식을 기반으로 작성한 코드이다.
change = int(input())
cnt = 0
coins = [500,100,50,10]
for i in range(4):
cnt += change//coins[i]
change %= coins[i]
print(cnt)해설 이 문제의 핵심은 '가장 큰 금액의 동전부터 거슬러 준다는 것'이다. 따라서 동전 리스트를 차례대로 불러와 거스름돈에 나눠준 뒤 그 나머지를 새로운 거스름돈으로 갱신하였다. 이를 모든 동전의 종류마다 시행해준다. 받은 거스름돈은 10의 배수이므로, 마지막에는 0원이 정확하게 떨어진다.
교재의 해설 본 연습 문제에서의 '최적의 해'를 찾는 것은 굉장히 쉬웠지만, 대부분의 코딩 테스트 문제에서는 이를 쉽게 찾지 못할 것이다. 내가 해당 문제의 해법을 찾았을 때 (아이디어를 떠올렸을 때), 그 해법이 정당한지 검토해야 한다. 이것저것 다양한 아이디어들을 고려해 본 뒤, 그 아이디어들에 대한 문제점들을 인식하고 최종적으로 최적의 해에 도달할 수 있어야 문제의 정답 판정을 받을 수 있는 것이다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
