[Python] 그리디(Greedy) 알고리즘

*해당 포스팅은 이것이 코딩 테스트다 with python(나동빈 지음) 교재를 공부하며 작성한 글입니다.

 

 

 

안녕하세요! 오늘은 그리디 알고리즘에 대해 알아보겠습니다.

 

그리디 알고리즘이란 단어 그대로 탐욕법이라고 할 수 있습니다.

 

코딩에서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미합니다.

 

그리디 알고리즘은 간단하고 유형이 다양하여 암기할 필요가 없지만 문제를 풀 때 창의력이 조금은 필요한 유형의 알고리즘입니다.

 

즉, 문제가 주어졌을 때 '어떠한 방식이 현재 상황에서 최선인가' 를 빨리 떠올리는게 중요합니다.

 

최단거리를 구하는 다익스트라 알고리즘의 같은 경우도 그리디 알고리즘에 해당하므로 그리디 알고리즘에 대해 잘 이해해 두는 것이 좋겠습니다.

 

물론 그리디 알고리즘이 모든 경우에서 최선의 알고리즘은 아닙니다.

 

 

그리디 알고리즘이 최선의 알고리즘이 아닌 경우를 예를 들면, 마시멜로 이야기를 생각해 봅시다.

 

마시멜로 이야기에서 아이는 마시멜로를 받고 15분을 기다리면 두배로 더 받을 수 있습니다.

 

하지만 여기에 그리디 알고리즘을 적용하게 되면 아이는 매 상황에 마시멜로를 한개 밖에 받지 못하게 됩니다.

 

기다리면 마시멜로를 훨씬 많이 받을 수 있는데 말이죠.

 

이처럼 그리디 알고리즘이 최선이 아닌 경우도 존재합니다.

 

오늘은 그리디 알고리즘이 적용 가능한 기본적이고 간단한 예시를 풀어보겠습니다.

 

 

거스름돈 문제

 

요즘은 카드로 다 계산해서 거스름돈에 대해 생각할 필요가 거의 없는 시대지만 그리디 알고리즘을 이해하는데 매우 좋은 예시이니 알아봅시다.

 

'카운터에서 점원이 거스름돈을 주는데 동전으로 거스름돈을 준다고 가정하고 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정합니다.

 

거슬러줘야 할 돈이 N원일 때 거슬러 줘야하는 동전의 최소 개수를 구하면 됩니다.

 

(이 때 N은 항상 10의 배수입니다.)

 

이 문제를 해결하는 아이디어는 매우 간단합니다.

 

바로 그냥 '가장 큰 단위의 동전 먼저 거슬러 주는 것' 입니다.

 

이를 코드로 작성하면 다음과 같습니다.

 

n=int(input())
count=0

coin_types=[500,100,50,10]

for coin in coin_types:
  count+=n//coin
  n%=coin

print(count)

 

금액을 입력받고 동전의 단위를 coin_types 에 넣습니다. 

 

반복문에서 금액을 가장 큰 단위의 동전부터 나눈 몫을 count 에 더합니다.

 

여기서 나온 몫은 그 단위의 동전의 개수를 의미합니다. 예를 들면 1110원일 경우 500원을 2개 주는게 최선의 선택이라고 할 수 있습니다.

 

이제 1000원은 거슬러 줬으니 거슬러줘야 하는 금액을 변경해줘야 하므로 금액을 그 단위의 동전으로 나눴을 때의 나머지 값으로 업데이트 해줍니다.

 

이 과정을 가장 작은 단위의 금액까지 반복하면 거슬러줘야할 동전의 최소 개수가 count에 저장되게 됩니다. 

 

 

*그리디 알고리즘의 정당성*

 

그리디 알고리즘으로 문제의 해법을 찾을 때는 그 해법이 정당한가를 생각해봐야 합니다.

 

방금 보여드린 거스름돈 예시를 그리디 알고리즘으로 해결 할 수 있었던 이유는

 

'가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문입니다.'

 

작은 단위의 동전으로 다른 동전의 단위가 나오는 예를 들어 보겠습니다.

 

돈을 800원을 거슬러 주는데 동전의 종류가 500원, 400원, 100원이라고 한다면 그리디 알고리즘으로 해결 할 경우 500원 1개, 100원 3개로 총 4개의 동전을 거슬러 줘야 합니다.

 

하지만 이 상황에서 동전을 최소로 거슬러 줄 수 있는 최선의 경우는 400원을 2개 거슬러 주는 것이 최선입니다.

 

이처럼 상황에 따라서 그리디 알고리즘이 적용되지 않을 수도 있으므로 그리디 알고리즘을 문제를 해결 할 때는

 

'문제 풀이를 위한 아이디어를 떠올리고 이 아이디어가 정당한지 검토할 수 있어야 합니다.'

 

 

 

지금까지 그리디 알고리즘의 기본 원리와 간단한 예제에 대해 알아보았습니다.