1일차 - 그리디

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

나중에 미칠 영향에 대해서는 고려하지 않는다.

 

여러 개의 데이터를 빠르게 정렬해야 하는 문제는 정렬 라이브러리 사용 방법을 알아야한다.

 

문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 라는 기준을 알게 모르게 제시해준다.

 

예제 3-1 거스름돈

거스름돈으로 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재할 떄, 손님에게 거슬러 줘야 할 돈의 동전의 최소 갯수를 구하라.

 

이 예제를 처음 접근했을 때에는 동전의 갯수가 최소여야 하므로 화폐단위가 큰 순서부터 나누기, 나머지 연산을 하면 되겠다는 생각을 했다.

아래 예시는 1,260원을 받았을 때이다.

def solution(n):
    answer = 0

    coins = [500, 100, 50, 10]
    
    for coin in coins:
        answer += n // coin
        n %= coin

    return answer

print(solution(1260))

 

위 코드는 책을 참고한 코드인데, 내가 구현했던 코드와 달랐던 점이 있다.

 

나는 coins 라는 list를 참고하지 않고, 500 100 50 10을 차례대로 나눴다.

coins라는 list를 통해 좀 더 가독성이 있어보이고, 깔끔해졌다.

 

 

그리디 관련 문제의 해법을 찾을때 정당한지 검토를 해야한다.

이 문제에서 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

 

 

예제 3-4 1이 될 때까지

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

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

이 문제에서는 K로 나누어 떨어질때까지 뺀 후, 나누기를 실행하면 될 것이다.

n, k = map(int, input().split())
answer = 0

while 1:
    target = (n // k) * k
    answer += (n - target)
    n = target

    if n < k:
        break
    answer += 1
    n //= k

answer += (n-1)
print(answer)