다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍

하나의 큰 문제를 해결하기 위해서, 여러 개의 작은 문제로 나누어 해당 문제들을 푼 후, 이를 쌓아올려 주어진 큰 문제를 해결하도록 하는 알고리즘이다.

이름의 유래?

Dynamic에는 별 뜻이 없고, 리처드 벨만이 “Dynamic” 이라는 단어가 멋있어 보여서 붙였다고 한다. Programming은 최적화 연구에서 최적의 프로그램을 찾을 때 쓰는 단어라고 한다.

이러한 다이나믹 프로그래밍(Dynamic Programming, DP)은 아래 두 가지 조건을 만족하는 문제에서 사용할 수 있다.

1. Optimal Substructure(최적 부분 구조): 전체 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되어야 한다.
2. Overlapping Subproblems(부분 문제 반복): 동일한 부분 문제가 반복해서 나타나야 한다.

 

다이나믹 프로그래밍으로 문제를 푸는 과정은 다음과 같다.

1. 부분 문제의 결과를 기록할 테이블 정의하기
2. 문제 내부의 변수 간 관계를 설명할 수 있는 점화식 만들기
3. 해당 문제를 풀기 위한 초기값 정하기

즉, 부분 문제를 계산해서 따로 저장하고, 반복적으로 해당 부분 문제의 결과를 필요로 할 때 해당 값을 사용하는 방식으로 풀 수 있다. 이러한 기법을 Memoization 또는 Caching이라고 한다.

 

DP를 구현하는 방식에는 Top-Down, Bottom-Up 두 가지 방식이 있다.

 

Top-Down

재귀함수를 통해서 큰 문제를 계속해서 쪼갠 후, 결과 값을 저장해서 이를 재활용하는 방식

피보나치 수열에서 $F(N)=F(N-1)+F(N-2)$을 해결할 때와 같이 특정 N에서의 피보나치 값을 반복해서 구해야 하는 경우, 제일 먼저 계산한 값을 테이블에 저장해서 나중에 이 값이 필요할 때 꺼내서 사용할 수 있다.

제일 아래의 문제부터 모든 경우를 확인하지는 않기 때문에, 문제 해결에 필요하지 않은 부분은 구하지 않아도 된다는 장점이 있다.

 

아래는 피보나치 수열의 N번째 숫자를 찾는 문제를 Top-Down 방식으로 해결한 코드이다.

dp = [0] * 10000

def fibo(N: int):
    if N <= 1:
        return N

    if dp[N] != 0:
        return dp[N]

    dp[N] = fibo(N-1) + fibo(N-2)
    return dp[N]

 

Bottom-Up

반복문을 이용해서 작은 문제에서부터 계산을 수행하고 이를 누적해 큰 문제를 해결하는 방식

DP[0]이 초기값일 때, 점화식을 통해서 DP[1], DP[2], ..., DP[N]까지의 값을 차례대로 구해나가는 방식이다.

Top-Down 방식과는 반대로 모든 부분을 다 구해서 이용해야 할 때는 Bottom-Up 방식이 유리하며, Top-Down 방식은 재귀적으로 계산하기 때문에 불필요한 스택 메모리 공간을 낭비할 수 있게 된다.

 

아래는 피보나치 수열의 N번째 숫자를 찾는 문제를 Bottom-Up 방식으로 해결한 코드이다.

def fibo(N: int):
    dp = [0] * 10000
    dp[1] = 1
    dp[2] = 1

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

    return dp[N-1] + dp[N-2]

 

Prefix Sum

Prefix Sum은 특정 구간의 합을 반복적으로 계산해야 할 때, 미리 처음부터 특정 위치까지의 합을 계산한 Table을 만들어서 이를 반복적으로 이용하는 것이다. 작은 부분 문제를 계산하여 이후에 재사용하기 때문에, Dynamic Programming의 일종이라고 볼 수 있다.

출처: https://venkys.io/articles/details/prefix-sum

Python으로 Prefix Sum을 구현한 코드는 다음과 같다.

def prefix_sum(num_list: List[int]):
    sum_list = [0] * len(num_list)
    sum_list[0] = num_list[0]

    for i in range(1, len(num_list)):
        sum_list[i] = sum_list[i-1] + num_list[i]

    return sum_list

위와 같이 구현했다면, sum_list 의 i번째 위치에는 num_list의 맨 처음 값부터 i번째 값까지 모두 더한 값이 저장된다. 이때, num_list의 a번째 위치부터 b번째 위치까지의 합을 구하려면 어떻게 해야할까?

 

우리는 num_list[a] + num_list[a+1] + ... + num_list[b-1] + num_list[b] 의 값을 구해야 한다. 이때 sum_list[i]가 sum_list[i] = num_list[0] + num_list[1] + ... + num_list[i]와 같이 정의되므로, 우리가 구하고자 하는 값은 다음과 같이 구할 수 있다.

sum_list[b] - sum_list[a-1] 
= (num_list[0] + ... + num_list[b]) - (num_list[0] + ... + num_list[a-1])
= num_list[a] + ... + num_list[b]

즉, num_list 내 모든 구간의 합을 $O(1)$의 단순 뺄셈으로 구할 수 있다.

 

왜 필요할까?

만약 N개의 원소를 가지고 있는 리스트의 특정 구간의 합을 M번 구해야 한다고 하자. 그렇다면 반복문으로 구간의 합을 M번 구했을 때는 해당 코드의 시간복잡도가 $O(NM)$이 될 것이다.

 

이때 위와 같이 Prefix Sum 알고리즘을 이용한다면 해당 테이블을 만들때의 시간복잡도는 $O(N)$이다. 또한, 특정 구간 [a, b] 의 합은 prefix_sum[b]-prefix_sum[a-1]로 계산될 수 있으므로 시간복잡도는 $O(1)$이 된다. 따라서 전체 시간복잡도는 $O(N)$이 된다.