그리디(Greedy) 알고리즘

그리디 알고리즘 (탐욕법)

그리디는 이름에서 알 수 있듯, 단순하고 탐욕적으로 문제를 해결하는 방법이다.
이때 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은것만 고르는 방법'을 의미한다. 그리디 알고리즘은 순간마다의 선택에 대해 지역적으로 최적이지만, 그 선택들이 합쳐져 전역적으로도 최적이어야한다.

그리디 알고리즘이 최적으로 작동되는 문제는 greedy choice property(탐욕적 선택조건)과 optimal substructure(최적부분 구조조건)이라는 두가지의 조건이 만족된다.

• 탐욕적 선택조건 : 선행된 선택이 이후의 선택에 영향을 주지 않는다.
• 최적부분 구조조건 : 문제에 대한 최적의 해가 부분문제에 대해서도 최적의 해여야한다.

거스름돈

그리디의 가장 대표적인 예는 거스름돈이다. 거스름 돈을 줄때는 가장 큰 화폐단위부터 내려가며, 결국 최대한 적은 양의 화폐를 주게된다. 1260원을 동전으로 건네 줘야할때, 500원, 100원, 50원, 10원 순서로 주면 최소한의 갯수로 거스름돈을 줄수 있다.

def getChange(totalMoney, count) :
	coinTypes = [500, 100, 50, 10]
    for coin in coinTypes :
    	count += totalMoney // coin  #해당 화폐로 거슬러 줄수있는 동전의 갯수
        n %= coin 	#해당화폐를 거슬러준 후 나머지값
	print(count)