그리디(Greedy) 알고리즘, 탐욕법

그리디(Greedy) 알고리즘이란

그리디 알고리즘 은 단순하지만 강력한 문제 해결 방법이다.
국내에서는 그리디 알고리즘 을 탐욕법 으로 소개된다.
따라서, 그리디 알고리즘 이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 을 의미한다.
그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘 예제

그리디 알고리즘 을 설명하기 위해 간단한 예를 들어본다.

음식점의 계산을 도와주는 점원이 있다. 이때 거스름돈을 거스러줘야 하는데 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 가정하자. 손님에게 거슬러줘야 하는 돈이 N 원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.

 

이 문제는 그리디 알고리즘을 풀 수 있는 대표적인 문제라고 한다.

바로 가장 큰 화폐단위부터 돈을 거슬러 주면 된다.

예를 들어, 1260 원을 거슬러줘야 한다면 다음과 같이 거슬러줄 수 있다.

 

1) 500원 동전 거슬러주기

500원 동전 2개를 거슬러줄 수 있다.

500원 x 2개 = 1000원 , 나머지 260원

 

2) 100원 동전 거슬러주기

100원 동전 2개를 거슬러줄 수 있다.

100원 x 2개 = 200원 , 나머지 60원

 

3) 50원 동전 거슬러주기

50원 동전 1개를 거슬러줄 수 있다.

50원 x 1개 = 50원 , 나머지 10원

 

4) 10원 동전 거슬러주기

10원 동전 1개를 거슬러줄 수 있다.

10원 x 1개 = 10원 , 나머지 0원

따라서, 500원짜리 동전 2개 , 100원짜리 동전 2개 , 50원짜리 동전 1개 , 10원짜리 동전 1개 로

총 6개의 동전이 필요하다.

이 문제를 코드로 확인하면 다음과 같다.

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

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

print(count)

 

 

그리디 알고리즘의 정당성

그리디 알고리즘은 모든 문제에 적용할 수 있는 것은 아니다.

대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’ 를 찾을 수 없을 가능성이 다분하다.

하지만 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이고 직관적이다.

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는

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

 

예를 들어 800원이 있는데 거슬러줄 수 있는 동전이 500원, 400원, 100원 이라고 가정했을 때

그리디 알고리즘으로 하면 500원, 100원, 100원, 100원 으로 총 4개의 동전이 된다.

하지만 최적의 해는 400원, 400원 으로 총 2개의 동전이 된다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.