greedy

greedy (그리디) 란

현재 상황애서 지금 당장 좋은 것만 고르는 방법

그리디 문제

거스름돈

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전을 무한히 사용할 수 있을 때

손님에게 거슬러 줘야 할 동전의 최소 개수를 구하라.

손님에게 거슬러 줘야 할 돈 = N

N = 1260
count = 0
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin
    n %= coin
print(count)

>>> 6

금액이 큰 동전부터 반복, 몫과 나머지를 사용하여 동전의 최소 개수를 구하며

시간 복잡도는 화폐의 종류가 K 개라고 할 때 O(K) 이다.

1이 될 때까지

어떠한 수 N 이 1이 될 때까지 아래 두 과정 중 하나를 반복 할 때 최소 횟수를 구하라.

1. N 에서 1을 뺀다.
2. N 을 K로 나눈다.

N, K = 25, 3
answer = 0

while True:
    # N 이 K 로 나누어떨어질 때까지 1씩 빼기
    target = (N // K) * K
    answer += N - target
    N = target

    # N 이 K 보다 작으면 (나눌 수 없을 때) break
    if N < K:
        break

    # K 로 나누기
    answer += 1
    N //= K

# 마지막 남은 수에서 1씩 빼기
print(answer + N - 1)

>>> 6

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수는 없기에 알고리즘 문제의 해법으로 그리디 알고리즘을 선택했을 때 정당한지 검토해야 한다.

거스름돈 문제에서 만약 화폐 단위가 500원, 400원, 100원이고 N = 800원 일때 위 알고리즘으로 풀이하면 500원 * 1개 + 100원 * 3개 = 4개가 된다.

하지만 400원 * 2개로 거슬러 주는 것이 최소 동전 개수이다.

이렇기에 그리디를 적용하기 전에 정당한지 검토를 할 수 있어야 한다.