[이것이 코딩테스트다 with 파이썬] 2_그리디

그리디 알고리즘(Greedy)

어떤 문제가 있을 때 탐욕적으로 문제를 푸는 알고리즘. 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
다만 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰(작은) 순서대로'와 같은 기준을 알게모르게 제시해준다.

예제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 돈이 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라. 단 거슬러 줘야할 돈 N은 항상 10의 배수이다.

1. 가장 큰 화폐 단위부터 거슬러 줄 때
2. 가장 최소한의 동전 개수로 거슬러 줄 수 있다.

# 예제 코드
import sys
sys.stdin = open('input.txt', 'r')
num = int(sys.stdin.readline())
coins = (500, 100, 50, 10)

cnt = 0
for coin in coins:
    cnt += num // coin
    num = num % coin

print(cnt)

• 시간복잡도 : O(N)

어떻게 풀어야할까

대부분의 그리디 알고리즘 문제에서는 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.
오랜 시간 그리디 알고리즘으로 풀 방법을 고민해도, 방법이 없다면 이후의 장에서 다루게 될 다이나믹 프로그래밍, 그래프 알고리즘 등으로 해결 할 수 있는지 재차 고민해봐야한다.