본문 바로가기

코딩 이야기/알고리즘 이야기

파이썬 탐욕(그리디) 알고리즘 사용하기

반응형

탐욕 알고리즘? 그리디 알고리즘?

 

탐욕 알고리즘은 이름하고 유사한 구조를 가진 알고리즘이다. 탐욕 알고리즘을 다른 말로 그리디 알고리즘 혹은 욕심쟁이 알고리즘이라고도 한다. 탐욕이라는 이름 그대로 지금 당장의 문제가 하나 주워졌을때, 나중은 고려하지 않고 지금의 가장 최적의 답을 도출하는 알고리즘이다.

 

한가지 상황을 예시로 들자면 사자성어 "조삼모사"가 떠오른다. 누군지는 기억안나는데 암튼 누군가가 원숭이들을 기르는데, 먹이가 부족해서 먹이를 줄여서 원숭이들에게 아침에 3개 저녁에 4개를 준다고 하자 원숭이들이 화를 냈다. 그러자 주인이 아침에 4개 저녁에 3개를 주겠다고 하니 원숭이들이 좋아한다는 그런 내용의 사자성어이다. 내용 그대로 당장 지금의 상황만 중요한 원숭이들이 그리디 알고리즘과 흡사하다.

 

탐욕 알고리즘의 장단점

(저 그래프에서 숫자는 노드 이름이 아닌 각 간선의 비용(거리)이다.)

저 보라색 원(노드)에서 주황색 원(노드)에 가야하는데, 최소거리로 가려면 어떻게 해야할까?

탐욕 알고리즘을 사용하면, 보라색 원에 위치하고 있을때, 비용(거리)가 가장 적은 파랑원으로 가야한다.

그후 연두색 원에 도착하고 또 선택을 해야하는데, 이때도 비용(거리)가 가장 적은 청록색원으로 가야한다.

그러면 주황색 원에 도착하고 총 비용(거리)는 3이므로, 가장 적은 비용(거리)로 도착했다.

 

이건 탐욕 알고리즘에 있어서 최적의 상황이고, 이제 안좋은 상황을 보자.

 

직접 힘들게 만든 그래프이다..

이번에는 작은 원에서 큰 원으로 갈때도 비용을 추가했다.

일반적인 사람이 보면 초록색원을 거쳐가는 비용(거리) 5의 경로를 선택할 것이다.

하지만 탐욕 알고리즘은 다르다.

탐욕 알고리즘으로 봤을때, 보라색 원에서 파랑색 원이 가장 비용이 적으므로, 파랑색으로 가야한다.

그러면 이제 파랑색원에서 주황색원으로 이동하게 되는데, 이때 비용이 7이 생겨서, 총 8이라는 비용이 생긴다.

이건 좀 극단적인 예시이긴하지만, 이런 상황에서는 탐욕 알고리즘을 사용해도 최적의 경로를 만들 수 없다.

이런 상황은 다익스트라 알고리즘을 사용하는 게 좋다.

(다익스트라 알고리즘은 나중에 정리할 예정)

 

탐욕 알고리즘 백준 문제 보기: 11047번

 

https://www.acmicpc.net/problem/11047

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

가장 대표적인 탐욕 알고리즘 문제이다. 대부분 탐욕 알고리즘을 설명할때, 이 문제를 언급한다.

나누기와 나머지 나누기를 사용해야한다는 점을 알게되면 매우 쉬워지는 문제이다.

 

import sys

n,k = map(int, sys.stdin.readline().split())

money = []
count = 0
for _ in range(n):
    money.append(int(sys.stdin.readline()))

for i in range(n-1,-1,-1):
    if money[i] > k:
        continue
    else:
        cc = k // money[i]
        k = k % money[i]

        count += cc

print(count)
반응형