[Algorithm] DP(Dynamic Programming), 동적 계획법

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 불린다.
이 알고리즘은 똑같은 연산을 계속 반복하지 않고, 한 번의 풀이만으로 해결하고자 하는 알고리즘이다.
큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결하고자 하는 방법이다.

❗  분할 정복 vs. 다이나믹 프로그래밍

둘의 공통점은 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결한다는 것이다.

분할 정복과 다이나믹 프로그래밍의 차이점은
DP의 경우, 나누어진 부분 문제가 중복되기 때문에, 재활용할 수 있다는 것이다.
분할 정복의 경우, 나누어진 부분 문제가 중복되지 않는다.

❗ 탑다운(Top-Down) vs. 바텀업(Bottom-Up)

탑다운 방식은 큰 문제를 해결하기 위해서 작은 문제를 호출하며 풀어나가는 방식
바텀업 방식은 작은 문제부터 해결하여 큰 문제를 해결하는 방식이다.

주로 재귀 함수와 메모이제이션을 사용하면 탑다운 방식, 
반복문을 사용하면 바텀업 방식이다.

---

➖ 피보나치 수열

먼저, 다이나믹 프로그래밍을 이해하기 위해 피보나치 수열에 대해 시작해보자면,

두 개의 항을 합하여 현재의 항이 되도록 하며 계속 이어지는 형태이다.
이러한 형태를 점화식을 이용하여 간단하게 표현한다.
점화식(Recurrence Relation)이란, 재귀식이라고도 하며 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계식을 의미한다. 
예를들어, 수열 { $a_n$ }이 있고, 각 항을 $a_n$이라고 한다.
$a_{n+1}\ =\ f(a_n)$ 에서 함수 f는 수열 { $a_n$ }의 점화식이라고 한다.
피보나치 수열의 점화식은 $a_{n+2}\ =f(a_{n+1},\ a_n)= a_{n+1}+\ a_n$ 으로 표현할 수 있다.
이 점화식 풀면, $a_n=a_{n-1}+a_{n-2}$로 나타낸다.
점화식을 재귀 함수를 사용하여 표현하면 간단하게 구현이 가능하다.

'''
< 피보나치 함수 >

- 점화식을 재귀 함수로 표현
'''
def fibo(x):
    if x==1 or x==2:
        return 1
    
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

fibo 한 번 호출에 두 번의 fibo 함수가 호출되면서 계산이 진행되므로 시간 복잡도는 $O(2^N)$이다.

T(N) = T(N-1) + T(N-2)     [ T(N-1) > T(N-2) ]
> T(N-2) + T(N-2) = 2 * T(N-2)
> 2 * 2 * T(N-4)
> 2 * 2 * 2 * T(N-6)
… > $2^{N/2}$ * T(0)

시간 복잡도가 $O(2^N)$이므로, 계산된 값을 다른 값을 구하기 위해 또 반복하게 되어 N의 값이 커질 수록 문제가 된다.
이러한 문제를 해결하기 위해 우리는 다이나믹 프로그래밍을 사용한다.
다이나믹 프로그래밍을 적용시키기 전 확인해야 하는 것은
큰 문제를 작은 문제로 나눠서 풀이할 수 있는지,
작은 문제를 해결한 값이 다른 큰 문제에서도 동일하게 포함이 되는지이다.

---

➖ 메모이제이션 | Top-Down

메모이제이션(Memoization)이란, 한 번 해결한 결과값을 메모리 공간에 저장해둔 후, 같은 식이 호출될 때 결과를 다시 꺼내오는 기법이다. 반복되는 계산을 하지 않기 때문에 훨씬 빠르게 계산이 진행된다.
위의 재귀 함수를 메모이제이션을 활용하여 풀어보면,

arr = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1

    if arr[x] != 0:
        return arr[x]

    arr[x] = fibo(x - 1) + fibo(x - 2)
    return arr[x]

print(fibo(99))

arr은 메모이제이션을 위해 한 번 계산된 값이 저장되는 저장소이다.
시간 복잡도는 한 번 구한 값은 다시 계산하지 않으므로 $O(N)$이다.

이미 계산된 결과값이 있다면, 그 값을 그대로 가져와서 더 이상 계산이 진행되지 않는다.
재귀 함수는 호출될 때마다 메모리의 스택에 쌓이게 되는데, 그렇다보니 계속 반복되면 메모리 부족으로 에러가 발생할 수도 있다. 또한, 재귀 함수 깊이에 대한 오류도 발생할 수 있다.
따라서, 반복문을 이용하면 성능이 더 향상된다.

---

➖ 반복문 | Bottom-Up

arr = [0] * 100

arr[1] = 1
arr[2] = 1

for i in range(3, 100):
    arr[i] = arr[i-1] + arr[i-2]

print(arr[99])

 

DP를 이용하는 문제는
부분 문제들의 중복 여부를 확인하기,
메모이제이션의 적용 생각하기,
Top-Down보다 Bottom-Up을 활용하기.

 

 

EX) 1로 만들기

1463번: 1로 만들기

점화식은 $a_i = min(a_{i - 1}, a_{i //2}, a_{i//3}) + 1$이다.

# 1로 만들기 (bottom-up)

N = int(input())

dp = [0 for _ in range(N+1)]  # N만큼의 리스트 생성

for i in range(2, N+1):  # 2부터 N까지 반복
    dp[i] = dp[i-1] + 1  # 3번 연산
    if i % 2 == 0:  # 3번보다 2번이 더 작은 경우
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:  # 3번보다 1번이 더 작은 경우
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])