[알고리즘] 그리디(Greedy) 알고리즘과 예제 (파이썬)

미남잉·2021년 12월 2일

algorithm datastructure python

📌 강의 바로가기

개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.

그리디 알고리즘

그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

예시로 짧게 보겠습니다.

아래 루트 노드가 있습니다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

여기서 최적해는 무엇일까요?

아래처럼 5 -> 7 -> 9 로 거쳐가면 21이란 최댓값이 나옵니다.

하지만 그리디 알고리즘은 어떻게 갈까요? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고릅니다.

루트 노드 5에서 시작하여 7, 10, 8 중 가장 큰 10을 선택하고, 4, 3 중에 4를 선택합니다.

그리디 알고리즘의 예시를 간단하게 보았는데요.

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.

하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 된다고 합니다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줍니다.

이제 예제로 그리디 알고리즘을 더 설명해보겠습니다.

예제: 거스름돈

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

문제 해설

동전의 최소 개수를 구해야 하는 문제이기 때문에, 가장 큰 화폐 단위부터 돈을 거슬러 주는 것입니다.

거스름 돈이 N원일 때, 500원으로 최대한 많이 거슬러주고, 순서대로 100원, 50원, 10원을 써서 거슬러주면 됩니다.

이제 N이 1,260 일 때의 예시를 확인해봅시다.

문제 풀이

[Step 1] 남은 돈: 1,260원

점원에게 1,260원이 있고 이제 손님에게 동전으로 거슬러줘야 합니다.

[Step 2] 남은 돈: 260원

500원 짜리로 거슬러 줄 수 있는 돈은 1,000원입니다. 즉, 500원 2개를 빼면 260원이 남습니다.

[Step 3] 남은 돈: 60원

100원 짜리로 거슬러 줄 수 있는 돈은 200원이었습니다. 이제 60원이 남았습니다.

[Step 4] 남은 돈: 10원

50원 짜리로 1개입니다. 이제 10원만 남았습니다.

[Step 5] 남은 돈: 0원

이제 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)