그리디 알고리즘

나동빈 그리디
탐욕법이라고도 불리는 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.

대표적인 문제로 거스름돈이 있다.
500원, 100원, 50원, 10원짜리 동전가지고 1260원을 거슬러 주어야 할 때, 손님에게 거슬러 주어야 할 동전이 최소 개수를 구한다고 해보자.
해당 문제의 경우에는 가장 큰 화폐 단위인 500원부터 차례로 거슬러 주면 될 것이다.
500원, 500원, 100원, 100원, 50원, 10원 -> 총 1260원

해당 방법이 최적의 해임을 보장하는 이유는 무엇일까?

큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올수 없기 때문이다. 만약 800원을 거슬러 줘야 하는데 화폐의 단위가 500원, 400원, 100원이라면 500원, 100원 x 3번이 될 것이다.
더 좋은 방법은 400원 x 2 인데도!

n = 1260
count = 0
coin = [500, 100, 50, 10]
for c in coin:
	count += n // c
    n %= c
   
print(count)

거스름돈의 시간 복잡도

화폐의 종류 k 개만큼 for문이 돌고 있다. 따라서 O(K)다.

1이 될 때까지

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.

내 풀이는 음.. 그냥 2번조건을 만족할 때까지 1번을 수행하다가 2번을 쭉 하고 다시 1번을 하다가 2번을 만족하면 2번을 쭉 하면 될거 같아! 하고 짰다.

import sys
N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())
count = 0

while True:
  if N % K == 0: N //= K
  else: N -= 1
  count += 1
  if N < K: break

print(count)

... 역시 더 좋은 방법이 바로 소개되었다.
나는 매번 1씩 루프를 돌며 까고 있지만
target = (N // k) * K 를 구해줌으로써 바로 2번을 만족시킨 뒤에,
count += (N - target) 으로 1씩 차감하는 것을 한 루프 안에서 끝냈다.