그리디(Greedy) 알고리즘

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

: 각 단계에서 최적이라고 생각되는 결정을 하여 최종적인 해답에 도달하는 알고리즘 ( 최적의 값을 보장하는 것이 아닌 최적의 ‘근사 값’을 목표 )

• Greedy - 탐욕스러운 →  욕심 많은 아이가 선택하듯이 계속 좋아 보이는 방법만 쫓는 것.

 

 

Case 1)  거스름돈 (그리디 사용 가능)

💡 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요.

• 큰 동전부터 거슬러주는 것이 항상 좋다 !
• 주어진 동전들이 전부 배수 관계에 놓여있기 때문 !

N = 78

use20 = N//20
N %= 20
use10 = N//10
N %= 10
use5 = N//5
N %= 5
use1 = N//1
N %= 1

print(f"20을 사용한 횟수: {use20}")
print(f"10을 사용한 횟수: {use10}")
print(f"5을 사용한 횟수: {use5}")
print(f"1을 사용한 횟수: {use1}")
print(f"사용한 동전의 총 개수: {use1 + use5 + use10 + use20}")

 

 

 

 

Case 2) 거스름돈 (그리디 사용 불가능)

💡 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요.

• 큰 동전부터 사용하게 될 경우 5 + 1 + 1 + 1이 되기 때문에 4개의 동전을 사용하게 된다.
  • 실제 답은 4 + 4 = 8 , 최소 동전 수는 2개 !

// 시간 초과 코드
N = 8
min_use = int(1e7)
use1, use4, use5 = 0,0,0

for a in range(N//1 + 1):
	for b in range(N//4 + 1):
		for c in range(N//5 + 1):
			if 1*a + 4*b + 5*c == N:
				if a + b + c < min_use:
					min_use = a + b + c
					use1 = a
					use4 = b
					use5 = c

print(f"1을 사용한 횟수: {use1}")
print(f"4을 사용한 횟수: {use4}")
print(f"5을 사용한 횟수: {use5}")
print(f"사용한 동전의 총 개수: {use1 + use4 + use5}")

 

 

---

 

📌정리

→ 매 순간에서의 최선의 선택이 문제의 최적해를 만족하는지 확인하여, 그리디 알고리즘을 적용할 지 확인하자 !