🌼알고리즘🌼 그리디 알고리즘

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

그리디 알고리즘 문제 유형

: 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준이 나타난다. 이런 기준은 정렬 알고리즘과 함께 짝을 이뤄 출제된다

 

그리디 알고리즘 예제

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

풀이

idea : 가장 큰 화폐 단위부터 돈을 거슬러 줘야함

가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그 다음 100원, 50원, 10원... 으로 거슬러 준다.

n = 1260
count = 0

# 동전의 유형
coin_types = [500, 100, 50, 10]

# 큰 것부터 나눠준다
for coin in coin_types:
	count = n // coin # 해당 동전 사용 갯수
    n %= coin
    
print(count)

 

그리디 알고리즘의 정당성

: 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유?
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 

예를 들어 화폐 단위가 500, 400, 100일 경우의 800원의 최소 동전 갯수는 400+400=>2개가 되어야 한다.

그러나 그리디 알고리즘으로 풀면 500+100+100+100 => 4개가 나온다.