[이코테] 3. 그리디

그리디

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

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

※ 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다

 

 

거스름돈 문제 예시

거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라 (N은 항상 10의 배수이다)

 

해결방법

가장 큰 화폐 단위부터 돈을 거슬러 준다

 

예를 들어 N이 1,260이라면 

500원	2개
100원	2개
50원	1개
10원	1개

 

 

파이썬 코드

n = 1260
count = 0

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

for coin in coin_types:
	count += n // coin  #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

 

 

시간 복잡도

화폐의 종류만큼 반복을 수행해야 하므로

화폐의 종류가 K개 이면 시간복잡도는 O(K)이다

 

 

그리디 알고리즘의 정당성

대부분의 문제는 최적의 해를 찾을 수 없을 가능성이 다분하다

하지만 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이다

그리디 알고리즘은 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디로 해결할 수 있는 이유는 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다