그리디(Greedy) 알고리즘

그리디 알고리즘

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 기준에 따라 좋은 것을 선택함

ex) 가장 큰 순서대로, 가장 작은 순서대로

- 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이룸

 

예제 - 거스름돈)

: 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때, 손님에게 거슬러줘야할 동전의 최소 개수 구하기

 

가장 큰 화폐 단위부터 돈을 돌려주자

1260원일때 -> 500 * 2 + 100 * 2 + 50 * 1 + 10 * 1 -> 총 동전의 개수 6개

# 시간 복잡도 o(k)
n = 1260
count =0

coin_type =[500,100,50,10]

for coin in coin_types:
	count += n // coin
    n %= coin
    
 print(count)

이 문제를 그리디 알고리즘으로 해결할 수 있는 이유?

 

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문