Algorithm 1. Greedy(그리디)

첫번째 알고리즘은 교재의 chapter3에 해당하는 그리디이다.

Greedy(그리디)는 쉽게 말해서 "당장 좋은 것만 선택하는 것 == 현재 상황에서 지금 당장 좋은 것만 고르는 것"

우선 그리디는 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는데, 그렇기 때문에 최종적(전역적)으로 최적이라는 보장은 없다. 그러나 대부분 그리디로 풀 수 있는 문제들은 "가장 큰 순서대로", "가장 작은 순서대로" 이런 조건을 제공해준다. 

 

그리디의 대표적인 문제로 [거스름돈]이 있다. 

거스름돈(p 87)

🔔 문제

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

---

이 문제가 전형적인 그리디문제로 동전을 최소로 주기 위해서는 큰 단위의 화폐 즉 여기선 500원,100,50,10원 순으로 많이 써야 동전의 갯수가 최소가 된다. 

🔔 정답 

n = int(input())

coin_type = [500, 100, 50, 10]
answer = 0

for coin in coin_type:
    answer += n // coin # 최대한 거슬러 줄 수 있는 만큼
    n %= coin

print(answer)

이 경우에는 화폐의 종류 k개만 반복하면 되기 때문에 가격과 상관없이 시간복잡도 O(k)이다.

이 문제를 그리디로 해결하려면 문제에서 주어진 동전들중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위의 동전들만을 모아서 다른 해가 나올 수 없기 때문에 그리디 적인 방법으로 풀 수 있다.

위 문제와 다르게 동전의 종류가 500,400,100원으로 주어졌다고 하자. 이 때 800원을 거슬러줘야할 때 위의 알고리즘을 통해서 그리디적인 방법으로 풀면 500,100,100,100이 되는데 실제 최적의 해는 400,400이다. 이 문제의 경우에는 500이 400의 배수가 될 수 없어 이러한 문제가 발생한다. 따라서 그리디로 문제를 해결하기 위해서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 현 문제에서 최적의 답으로 이어지는지를 생각해야 한다. 

 

본 책에 기재된 그리디 예시 문제는 아래와 같다.

큰 수의 법칙-[이것이 취업을 위한 코딩 테스트다]

 

숫자 카드 게임-[이것이 취업을 위한 코딩 테스트다]

 

1이 될 때까지-[이것이 취업을 위한 코딩 테스트다]

+ 추가적으로 예전에 정리한 그리디 알고리즘 정리글도 첨부하였다.

Algorithms-[Greedy] (백준 #11047 [동전0])