September 3, 2021

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 대부분의 출제자가 최적의 방법을 정해놓고 문제를 만들기 때문에 핵심 아이디어를 추론하는 것이 중요
• 핵심 아이디어를 생각했다면 정당성(좋아보이는 것을 반복하여 선택해도 최적의 해를 구할 수 있는지)을 분석해야 한다.

그리디 알고리즘 예제 - 거스름돈

문제

거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 존재한다고 가정한다. 손님에게 돌려주어야 할 거스름돈이 N원일 때, 거슬러 주어야 할 최소한의 동전 갯수는?

소스코드

n = 1260
count = 0

coinList = [500, 100, 50, 10]

for coin in coinList:
    count += n // coin
    n %= coin

print(count)

핵심 아이디어

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

정당성 분석

동전의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 더 작은 해가 나올 수 없다.

시간 복잡도 분석

K를 화폐 종류의 갯수라고 하자. 이 풀이의 시간 복잡도는 O(K)로 화폐 종류의 수에 의존한다.