[파이썬(Python)] 그리디 알고리즘

나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다.

 

현재 상황에서 가장 좋아 보이는 것만 선택하는 알고리즘입니다. 

직역해서 탐욕스러운 알고리즘으로, 탐욕법이라고도 합니다.

그리디 알고리즘 유형은 특별히 암기를 할 유형이 정해져 있는 것은 아니어서, 문제마다 아이디어를 낼 수 있어야 합니다.

출제 빈도는 높지 않지만, 다양한 문제가 그리디 알고리즘 문제로 분류가 됩니다.

 

예제

어떤 금액을 500원, 100원, 50원, 10원 동전으로 거슬러 줄 때, 동전의 최소 개수를 구하시오

 

이 문제는 가능한 한 큰 액수의 동전을 사용해야 합니다. 가장 큰 액수인 500원 부터 시작해서 해당 금액을 깎아 나가는 방식입니다.

 

n = 1850
cnt = 0

coins = [500, 100, 50, 10]

for coin in coins:
	cnt += n // coin
	n %= coin

print(cnt)

위 문제의 시간복잡도는 거슬러 줄 금액이 아닌 동전 종류의 개수에 의존합니다. 동전의 종류 개수 만큼 반복해서 해당 동전으로 금액인 n을 나누면서 문제를 해결하기 때문입니다.

 

이 문제를 푸는 데에 탐욕법을 사용하는 것은 타당해 보입니다. 그러나 문제에서 800원을 거슬러야 하고, 500원, 400원, 100원을 사용 가능한 동전 종류로 제공하면 말이 달라집니다. 탐욕법에 따르면 500원, 100원 x 3, 총 4개의 동전이 필요하지만, 정답은 400원 두 개입니다.

 

기존 문제에서 탐욕법이 가능했던 것은 각 요소들이 서로 나누어 떨어지기 때문입니다. 서로 배수 또는 약수들로 구성되어 있지 않은 경우에는 탐욕법을 사용할 수 없습니다. 이처럼 탐욕법으로 쉽게 풀 수 있을 것 같은 문제로 보여도 그것이 틀릴 가능성이 있다는 것을 항상 염두해야 합니다.

 

앞으로 문제를 풀 때 딱 떠오르는 알고리즘이 없다면 탐욕법으로 먼저 생각해보는 것이 좋습니다. 탐욕법으로도 뾰족한 방법이 떠오르지 않을 때는, 다이나믹 프로그래밍이나 그래프 알고리즘을 대안으로 이용해봅니다.