[방학의 PS] 다이나믹 프로그래밍(DP) - BOJ_1463

오늘은 새로운 알고리즘에 대해서 이야기해 보겠습니다. 바로 다이나믹 프로그래밍이라고 불리는 알고리즘입니다. 혹시 처음 들어 보신 분이 계시다면, 이름이 생소하고 고급져서 왠지 어렵게 느껴지실 수도 있을 것 같습니다. 그러나 걱정할 것 없습니다. 사실 다이나믹 프로그래밍(이하 dp)이라는 이름은 알고리즘의 개발자가 펀딩을 따내기 위해 일부러 있어 보이게 작명한 네이밍이거든요ㅎㅎ. 실상은 아주 단순한 알고리즘을 의미합니다.

 

dp의 핵심은 문제를 반복되는 단계로 쪼개어 앞선 단계의 값을 뒤의 단계에서 활용한다는 것입니다. 이 말의 의미를 피보나치 수열을 예로 들어 자세히 알아보겠습니다.

 

우리가 코딩을 통해 피보나치 수열의 n번째 수를 구하는 경우, 다음과 같이 재귀를 주로 활용합니다.

 

def fib(n):
    if n < 3:
        return 1
    else:
        return fib(n-1) + fib(n-2)

 

그러나 이 알고리즘은 다소 비효율적입니다. 왜냐하면 중복되는 값을 고려하지 않기 때문입니다. 예를 들어 fib(n)을 구하는 경우, fib(n-1)과 fib(n-2)가 필요합니다. 그리고 fib(n-1)을 구하는 경우 fib(n-2)와 fib(n-3)이 필요합니다. 즉 fib(n)을 구하기 위해서 fib(n-2)는 두 번 필요한데, 재귀를 통해 구하는 경우에는 fib(n-2)를 두 번 계산하게 되어 낭비가 발생합니다. 만약 fib(n-2)를 처음 구했을 때, 어딘가에 저장해 두었다가 또 fib(n-2)를 계산해야할 때 불러온다면, 시간을 훨씬 단축할 수 있을 것인데 말입니다.이것이 바로 dp에서 앞선 단계의 값을 뒤의 단계에서 활용한다는 것의 의미입니다.

 

그렇다면 이번에는 dp를 통해 피보나치 수열을 구하는 코드를 살펴 보겠습니다. dp도 종류가 여러 가지 있는데 여기서는 bottom-up 방식을 다뤄 보겠습니다. 왜냐하면 모든 방식을 다룬다면 글이 너무 길어지고, bottom-up 방식이 제가 생각했을 때 좀 더 직관적일 뿐더러, 뒤에 첨부할 문제에서 제가 활용했던 방식이기 때문입니다.

 

def fib(n):
    fib_sequence = [0, 1, 1] + [0] * (n - 2) # fib_sequence[n]이 곧 수열의 n번째 수

    for i in range(3, n + 1):
        fib_sequence[i] = fib_sequence[i - 1] + fib_sequence[i - 2] # 점화식
    
    return fib_sequence[n]

 

코드가 왠지 익숙하지 않으신가요? 이는 바로 인간이 피보나치 수열을 구할 때 생각하는 방식과 거의 똑같습니다. 앞서 구한 수를 기억해서 뒤에서 활용하는 방식이죠. 차이점이 있다면 사람은 계산이 이루어질 때마다 메모리를 할당하지만 컴퓨터는 미리 n+1개의 메모리(배열)를 할당한다는 것 뿐입니다.

 

혹자는 dp의 정수를 점화식으로 보기도 합니다. 이는 위에서 점화식 부분이 알고리즘의 핵심을 이루고 있기 때문인 것 같습니다.

 

---

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

n = int(input())
arr = [-1, 0, 1, 1, 2, 3] + [-1] * (n - 5)
for i in range(6, n + 1):
  basket = []
  basket.append(arr[i - 1] + 1)
  basket.append(arr[i - 2] + 2)
  if i % 3 == 0:
    basket.append(arr[i // 3] + 1)
  if i % 2 == 0:
    basket.append(arr[i // 2] + 1)
  arr[i] = min(basket)

print(arr[n])