[Python] 그리디 알고리즘을 파헤쳐 보자! (1이 될 때까지)

그리디 알고리즘이란?

그리디 알고리즘 또는 탐욕벅이라고 불린다. 현재 상황에서 가장 좋은 정답을 찾는 알고리즘이지만, 항상 최적의 해를 보장할 수 없다. 코딩 테스트에서는 대부분 그리디 알고리즘을 통해 얻은 해가 최적의 해가 되는 상황을 부여하기 때문에 가장 최적의 해를 찾아 문제를 풀 수 있어야 한다.

 

여러가지 예시를 보고 이해를 해보자.

문제

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

 

1-1. N에서 1을 뺍니다.

1-2. N을 K로 나눕니다.

입력

25 4

출력

5

정답

import sys

n, k = list(map(int, sys.stdin.readline().strip().split()))
result = 0

while True:
     # target은 n에서부터 k로 나눌 수 있는 가장 가까운 수
     target = (n // k) * k
     result += n - target
     n = target

     if n < k:
          break

     # k로 나누기
     result += 1
     n //= k

# n을 1로 만들기 위한 식
result += n - 1
print(result)

Tip

N을 1로 만들기 위해서는 1씩 빼기를 하는 것보다 K로 나누는 것이 기하급수적으로 N이 작아지기 때문에 우린 K로 나눌 수 있다면 나누어야 한다.

 

# n = 25, k = 4
target = (n // k) * k
# target = 24

 

여기서 k로 나눌 수 있는지에 대한 조건문 대신 약간의 테크닉을 사용하여 n을 k로 나누어 떨어질 수 있는 가장 가까운 수가 나오게 된다. 만약, n이 k로 나누어질 수 있는 상태라면 똑같은 숫자가 반환되게 된다.

# n = 25, target = 24
result += n - target
# result = 1

N에서 K로 나눌 수 있는 수인 target을 빼주면 -1를 몇 번 했는지 알 수 있게 되고, 그것을 result에 카운트를 해준다.

# N을 K로 나누기
result += 1
n //= k

N은 K로 나눌 수 있는 수로 변경 되었으니 result에 1 카운트 후 K로 나누어 준다.

if n < k:
	break

N이 K보다 작다면 나누기를 더 이상 할 수 없는 의미이기 때문에 반복문을 탈출하게 된다.

# result = 4, n = 2
result += n - 1
# result = 4 + 1

N과 1 사이에 차이를 구해 마지막으로 -1를 몇 번 해야하는지 카운트하여 result에 더해준다.

 

Reference

본 그리디 알고리즘 문제 예제 및 개념은 나동빈 (이코테 2021 강의 몰아보기) 2. 구현 & 그리디 구현을 참고합니다.