들어가며
이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다. 그리디 알고리즘에서 그리디란 탐욕이라는 영어 단어입니다. 탐욕이라는 의미는 욕심이 많고, 놀부같다는 생각이 들지도 모르겠습니다만, 그리디 알고리즘에서의 탐욕은 그렇게 부정적인 의미가 아닙니다. 그렇다면 본격적으로 그리디 알고리즘이 무엇인지 알아보겠습니다.
Greedy Algorithm
그리디 알고리즘이란 매 순간 가장 최선의 선택을 하여 정답을 탐색하는 알고리즘입니다. 가장 보편적인 예시로 잔돈을 거슬러주는 예제를 생각할 수 있습니다.
A라는 인물은 카운터를 보는 직원입니다. 카운터 직원은 손님이 계산을 위해 건내준 돈이 물건의 가격보다 높다면, 잔돈을 거슬러줘야 하는데요. 이를 위해서 카운터에는 잔돈으로 건낼 수 있는 무한한 양의 10원, 50원, 100원, 500원, 1000원, 5000원, 10000원, 50000원이 있다고 하겠습니다. 손님에게 거슬러줘야 하는 금액 N을 잔돈의 갯수가 최소가 되게 거슬러줘야 하는 상황이라고 하겠습니다.
예를 들어, 손님에게 거슬러줘야 하는 돈이 500원이라면 100원짜리 5개와 500원짜리 1개를 손님에게 드릴 수 있지만, 최소한의 잔돈 갯수 원칙을 지키기 위해 500원짜리 1개를 손님에게 드려야하고 1을 출력할 수 있습니다.
이런 상황은 그리디 알고리즘을 이용해서 해결할 수 있습니다. 손님에게 건내주는 잔돈이 최소가 되기 위해서는 최대한 금액이 큰 잔돈을 주면 됩니다. 풀이 코드를 보며 설명드리겠습니다.
n = int(input())
money = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
result = 0
for m in money:
result += n // m
n %= m
print(result)우선, 잔돈으로 사용할 수 있는 지폐들을 배열로 선언합니다. 그리고 반복문을 이용하여 result 변수에 n을 m으로 나눈 몫을 더해줍니다. 그리고 n은 m으로 나눈 나머지로 갱신하여 준다면, 최적의 해를 구할 수 있습니다.
처음 반복문에서는 m은 50000입니다. n을 50000으로 나눈 몫을 result에 더해주고, n을 50000으로 나눈 나머지값으로 갱신합니다. 만약 잔돈이 지페값보다 작아도 연산에 영향이 발생하진 않습니다. 이렇게 최소가 된 잔돈의 갯수를 구할 수 있습니다.
주의사항
하지만, 그리디 알고리즘을 이용할 경우 그리디 알고리즘을 이용해서 해결할 수 있다는 정당성이 있어야 합니다. 그말은 곧, 단순히 가장 좋아보이는 것을 선택해도 문제의 해를 구할 수 있는지 정당한 이유가 필요하다는 뜻입니다.
