D.P.

많은 사람들이 DP 하면 떠오르는 것은 요즘 유행 하는 넷플릭스 시리즈의 D.P.일 것이다.

하지만 알고리즘 공부를 좀 했다 하는 사람들은 드라마가 아닌 알고리즘 Dynamic Programming을 생각할 것이다.
최근 알고리즘 공부를 하면서 처음 접해 보았는데 꽤 고생좀 했기때문에 Dynamic Programming 알고리즘에 대해 알아볼 것이다.

Dynamic Programming은 DP, 동적 계획법이라고도 말한다.

DP 알고리즘의 원리는 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

Top-down vs Bottom-up

다이나믹 프로그래밍 문제를 푸는 방법은 Top-down과 Bottom-up이 있다.
두 방법 모두 큰 문제를 여러 개의 부분 문제들로 나누어 풀지만, Top-down은 가장 큰 문제를 방문 후 작은 문제를 호출 하여 답을 찾는 방식이고, Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. 보통 top-down은 재귀 호출을, bottom-up은 반복문을 이용해 구현한다.

---

문제 1

가장 대표적인 문제는 피보나치 함수이다. Baekjoon 1003번 문제를 예로 보자면

Solution

import sys
T = int(sys.stdin.readline())
zero = [1,0,1]
one = [0,1,1]
def fibonacci(num):
    if len(zero) <= num:
        for i in range(len(zero), num+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print(zero[num],one[num])
for i in range(T):
    N = int(sys.stdin.readline())
    fibonacci(N)

처음 문제를 접했을때는 재귀 함수를 구현하고 0과 1이 나왔을 때의 갯수를 세서 출력하려했다. 하지만 시간초과가 나와 처음부터 문제 접근을 다시 해야 했다.
배열에 0과 1이 나온 횟수를 저장해, fibo(n-1)과 fibo(n-2)의 0,1 갯수를 다시 세지 않고 fibo(n)의 0,1 갯수를 알 수 있는 알고리즘을 작성했다.

다음은 다른 DP문제인 Baekjoon 1463번 문제이다.

---

문제 2

Solution

import sys
N = int(sys.stdin.readline())
dp = [0 for _ in range(N+1)]
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[N])

위 문제를 처음 접했을 때 역시 3이 나눌 수 있는 수 중 가장 큰 수이어서 3을 나누는 것을 우선으로 두고, 2를 나누고, -1을 해주는 식으로 문제를 접근했지만 답이 아니었다. 때문에 이번에도 배열을 만들고 N까지의 모든 답을 구하면서 그 이전의 값은 계산하지 않는 최소한의 수행으로 답을 해결했다.

대부분의 DP 문제들은 메모리를 적절하게 사용하여 수행 시간 효율을 비약적으로 향상 시키는 것을 목적으로 두고 있기 때문에 일반적인 알고리즘 풀이로 풀게 된다면 시간초과가 된다.

DP 알고리즘 같이 생각을 한번 더 하게 만드는 문제를 풀면서 아직 배워야 할 것이 많다는 것을 느꼈다. 글을 마치며 DP알고리즘 문제를 풀다가 머리가 아프다면 넷플릭스 오리지널 D.P.를 보며 쉬어가는것도 나쁘지 않다고 생각한다.