[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

728x90

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

Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의 가장 좋아 보이는 것만 선택하기 때문에 나중에 미칠 영향은 고려하지 않아 지역적으로는 최적이지만 최종적(전역적)인 답에 도달했다고 해서 그것이 최적해라는 보장은 없습니다.

만약 그리디 알고리즘을 적용하여 위와 같은 트리에서 거쳐 가는 노드 값의 합을 최대로 만든다고 하면 순간의 선택만 고려하기 때문에 3 -> 7 -> 9라는 경로로 해는 19가 됩니다.

하지만 실제 최적해는 21(3 -> 5 -> 13)로 이는 그리디 알고리즘이 최적의 해를 보장할 수 없음을 보여줍니다.

따라서 그리디 알고리즘을 적용하려면 지역적으로 최적이면서 최종적으로 최적 이도록 조건을 만족해야 합니다.

그리디 알고리즘의 조건

1) 탐욕적 선택 속성(Greedy Choice Property)

앞의 선택이 이후의 선택에 영향을 주지 않습니다. 지역적 선택이 전체 문제의 최적해를 도출할 수 있어야 합니다.

2) 최적 부분 구조(Optimal Substructure)

문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성됩니다. 문제를 해결하는 모든 단계에 대해서 해당 단계의 최적해가 도출되어야 합니다.

ex) 부분 문제에서 A에서 B까지의 최단 경로 X를 구했을 때 X는 모든 문제에서 최단 경로

문제 적용

거스름돈 문제

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

이 문제에 그리디 알고리즘을 어떻게 적용시켜 풀 수 있을까요? 바로 가장 큰 단위의 동전부터 탐욕적으로 거슬러주면 최소 개수의 동전으로 거슬러 줄 수 있습니다.

N이 2320 일 때의 예시를 보겠습니다.

1) 위에서 말한대로 가장 큰 단위의 동전부터 거슬러주면, 가장 큰 단위의 동전은 500원이므로 거슬러 줄 동전은 500원짜리 동전 4개이고, 320원이 남습니다.

2) 320원은 그 다음 큰 단위의 동전인 100원짜리 동전 3개로 거슬러 줄 수 있고, 20원이 남습니다.

3) 20원은 그 다음그다음 큰 단위의 동전 50원보다 작으므로 그다음으로 큰 10원짜리 동전 2개로 동전을 모두 거슬러 줍니다.

4) 500원 x 4개, 100원 x 3개, 10 x 2개, 총 9개로 동전을 최소로 하여 거슬러 주게 됩니다.

정당성 분석

가장 큰 동전 단위부터 돈을 거슬러 주는 것이 과연 최적의 해를 보장해줄까?

거스름돈으로 사용할 500원, 100원, 50원, 10원은 모두 큰 단위가 작은 단위의 배수로 이루어져 있기 때문에 작은 단위의 동전들을 종합하여 다른 해가 나올 수 없습니다.

만약 1200원을 거슬러 줘야 하는데 거스름돈으로 사용할 동전이 700원, 600원, 100원이고 위처럼 그리디 알고리즘을 적용하면 700원 x 1개, 100원 x 5개를 최적의 해로 계산을 합니다. 하지만 실제 최적의 해는 600원 x 2개로 이는 정당하게 적용이 되지 않았음을 보여줍니다.

따라서 그리디 알고리즘을 적용하려면 아이디어가 정당한지 검토할 수 있어야 합니다.

코드

n = 2320
cnt = 0

# 큰 단위의 동전부터 적용하기 위해 순서대로
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    cnt += n
    n %= coin

# 9 출력
print(cnt)

이 코드는 동전 단위의 종류만큼 반복을 수행하기 때문에 종류의 수를 k 개라고 할 때 시간 복잡도는 O(k)로 거슬러 줘야 하는 금액의 크기와는 무관합니다!