[알고리즘] 그리디 알고리즘

그리디 알고리즘이란?

한국어로 탐욕이라는 뜻의 그리디 알고리즘(Greedy Algorithm)은 단순하만 강력한 문제 해결 방법이다. 탐욕적으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이 바로 탐욕법, 그리디 알고리즘이다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

그리디 알고리즘은 다른 알고리즘과는 달리 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 유형의 문제이다. 다음번에 다룰 최단 경로, 정렬 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다.

 

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

 

그리디 알고리즘의 대표적인 문제가 바로 거스름돈 문제이다. 우리가 만약 33700원 짜리 물건을 구매한 후 거스름돈을 받을때는 가장 작은 동전의 갯수를 받고 싶어한다. 이때 사용되는게 바로 그리디 알고리즘이다. 33700원을 지불하기 위해 5만원권 한장을 지불했으면 거스름돈 16300원을 받아야 한다. 물론 100원 짜리 163개를 받을수도 있지만 그걸 원하진 않을것이다. 그래서 우리는 10000원권 한장과 5000원권 한장, 1000원권 한장과 그리고 100원짜리 3개를 받는다. 

'가장 큰 화폐 단위부터' 돈을 거슬러 주는 것'이 거스름돈 문제를 푸는 방법이다.

 

코드로 작성해보며 아래와 같다.

#Python
n = int(input()) # 거슬러야 하는 돈을 입력받는다.
cnt = 0

# 큰 단위의 화폐부터 차례대로 확인
list = [50000, 10000, 5000, 1000, 500, 100]

for coin in list:
	cnt += n//coin # 해당 화폐로 거슬로 줄 수 있는 동전의 개수 세기
    n %= coin # 거슬러준 동전은 제외시켜줌. 즉 남은 돈 갱신
   
print(cnt)

 

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의  해'를 찾을 수 없을 가능성이 다분하다. 거스름돈의 문제 같은 경우 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 문제를 해결할 수 있었다. 

 

예를 들어 800원을 거슬러 줘야 하는데, 화폐단위가 500원, 400원, 100원인 경우를 생각해보면 이때는 그리디 알고리즘으로 해결하지 못한다는 걸 알 수 있다. 현재 가장 큰 단위인 500원으로 하나 거슬러 주고 남은 금액 300원을 100원짜리 세개로 거슬러 주면 총 4개(500: 1, 100: 3)의 동전을 받게 된다. 하지만 이 경우 400원 짜리 동전 두개로 거슬러 받는 것이 가장 적은 동전을 받는 방법이다. 

 

어떤 코딩 체스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후에 다뤄볼 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결할 수 있는 지를 고민해보도록 하자!

 

 

'이것이 코딩 테스트다' 를 읽고 정리한 내용입니다.