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

1. 그리디 알고리즘(탐욕법)이란?

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
쉽게 말하면 탐욕스럽게 최고의 선택만 취하는 것을 말합니다.

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
• 그리디 해법은 그 정당성 분석이 중요합니다.
  단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

✔️ 그리디 알고리즘은 항상 최적의 해를 보장하지 않습니다.

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다.

 

트리에서 경로를 이동하면서 각 노드의 합이 최대가 되는 경우를 생각해봅니다.

실제 최적의 해 / 그리디 알고리즘의 해

실제 각 노드의 합이 최대가 되는 경우는 왼쪽과 같습니다. 하지만, 그리디 알고리즘을 사용하여 매순간 최적의 값을 선택하게 된다면 오른쪽과 같은 경로가 설정되고 최적의 해가 아닙니다.

이처럼 그리디 알고리즘은 항상 최적의 해를 보장하는 것은 아니지만 속도가 굉장히 빠르기 때문에 자주 사용됩니다. 그렇기 때문에 항상 최적의 해를 보장하도록 특수한 조건을 만족시켜줘야 합니다.

 

 

2. <문제> 거스름돈

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

최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됩니다.

• N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줍니다.
  이후에 100원, 500원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됩니다.
• N = 1,260일 때의 예시를 확인해 봅시다.

STEP 0)

화폐 단위	500	100	50	10
손님이 받은 개수	0	0	0	0

STEP 1)

화폐 단위	500	100	50	10
손님이 받은 개수	2	0	0	0

STEP 2)

화폐 단위	500	100	50	10
손님이 받은 개수	2	2	0	0

STEP 3)

화폐 단위	500	100	50	10
손님이 받은 개수	2	2	1	0

STEP 4)

화폐 단위	500	100	50	10
손님이 받은 개수	2	2	1	1

 

결론적으로 손님은 동전의 최소 개수를 받고 최적의 해를 도출합니다.
가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유가 무엇일까?

• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.  만약에 800원을 거슬러 주어야 하는데 화폐단위가 500원, 400원, 100원이라면 최적의 해를 보장할 수 없습니다.

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

 

코드 풀이

n = 1260
cnt = 0

# 큰 단위의 화폐부터 차례대로 확인하기
arr = [500, 100, 50, 10]

for i in arr:
  cnt = cnt + (n // i) # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
  n = n % i # 거슬러주고 남은 나머지
  
print(cnt)

 

시간 복잡도

• 화폐의 종류가 K라고 할때, 소스코드의 시간 복잡도는 O(K)입니다.
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받습니다.