[자료구조/알고리즘 이론] 다이나믹 프로그래밍(Dynamic Programming, DP)

다이나믹 프로그래밍

다이나믹 프로그래밍은 하나의 문제를 단 한 번만 풀도록 하는 것이 핵심입니다. 어떤 특정 범위까지의 값을 구한다고 할 때, 그것을 하위나 상위 등 다른 범위의 값을 이용하여 효율적으로 푸는 알고리즘이 바로 다이나믹 프로그래밍, 혹은 동적 계획법입니다.

 

현재 주어진 문제를 더 작은 문제로 나누어 각 부분 문제의 값을 계산하고, 최종적인 결과 값을 도출한다는 점에서 분할 정복 알고리즘과 비슷하지만, 명백한 차이점이 있습니다.

 

다이나믹 프로그래밍 vs 분할 정복 알고리즘

다이나믹 프로그래밍은 분할 정복 알고리즘과 다르게 동일한 계산을 할 경우 계산한 결과를 미리 저장해 두었다가, 필요한 경우 꺼내서 사용합니다. 즉 메모리라는 공간 자원을 활용하여 불필요한 계산을 줄여 계산에 소요되는 시간을 줄입니다. 이렇게 동일한 문제를 여러 번 계산할 것을 가정하여 작은 문제를 계산한 값을 저장하여 필요 시 꺼내어 활용하는 방법에는 메모이제이션(Memoization)과 타뷸레이션(Tabulation), 총 두 가지 방법이 있습니다. 🧠메모리제이션(Memorization)이 아니라 📝메모이제이션(Memoization)입니다! 

 

메모이제이션(Memoization)

메모이제이션은 재귀적 접근을 기반으로 하는 탑다운(Top-Down) 접근 방식을 가지는 캐싱 기법입니다. 먼저 큰 문제를 해결하기 위해 작은 문제로 쪼개는 과정을 거치게 되는데, 이 쪼개는 과정을 재귀로 구현합니다. 그렇게 쪼갠 결과 값을 캐시(메모리 테이블)에 저장합니다. 이 값을 저장하는 캐시는 주로 배열로 구현합니다. 나중에 동일한 계산을 해야 할 경우 이전에 미리 저장한 값을 캐시에서 꺼내 사용합니다.

 

타뷸레이션(Tabulation)

타뷸레이션은 반복적 접근을 기반으로 하는 바텀업(Bottom-Up) 접근 방식을 가지는 캐싱 기법입니다. 메모이제이션과는 다르게 먼저 작은 문제부터 시작하여 반복을 통해 테이블을 채워나가고 모든 부분 문제를 미리 계산하여 테이블에 저장합니다. 즉 정해진 순서가 명확하며 순차적 탐색을 통해 테이블을 채워나갑니다. 메모이제이션이 큰 문제를 작은 문제로 재귀하며 쪼개서 문제를 해결한다면, 타뷸레이션은 시작부터 작은 문제로 시작하여 큰 문제를 해결하는 것입니다. 이해가 잘 가지 않는다면 아래의 예시 코드를 살펴봅시다.

 

다이나믹 프로그래밍 구현

다이나믹 프로그래밍 알고리즘을 적용할 수 있는 문제로는 0-1 냅색 문제, LIS 문제 등 몇 가지가 있지만 대표적인 DP 문제인 피보나치 수열을 통해 다이나믹 프로그래밍을 적용해 봅시다.

 

피보나치 수열의 경우 첫째 및 둘째 항이 1이며 그 뒤의 항은 바로 앞 두 항의 합인 수열입니다. 우리가 n번째 항의 결과 값을 구한다고 생각할 때 수식은 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)가 될 것입니다. n 번째 항을 구하기 위해 재귀를 통해 n-1 번째 항을 구하고, n-1 번째 항을 구하기 위해 재귀를 통해 n-2 번째 항을 구하고... 앞의 메모이제이션 기법과 유사하지 않나요? 맞습니다. 메모이제이션을 적용해서 재귀를 통해 풀 수 있습니다.

https://news.samsungdisplay.com/23402/

피보나치를 적용할 경우 아래의 사진과 같이 재귀함수가 호출되게 됩니다. 빨간색과 초록색으로 칠해진 재귀함수의 경우 같은 재귀함수를 여러 번 호출하게 되어 불필요한 연산을 반복하게 됩니다. 이미 fibonacci(8)의 경우 이미 fibonacci(9)에서 값을 구했을 텐데, fibonacci(10)를 호출하며 같은 연산을 반복하게 되는 것이죠. 이러한 불필요한 반복 연산을 막기 위해 연산한 값을 저장합니다.

 

메모이제이션을 사용할 경우 아래와 같이 결과 값을 dp라는 배열에 저장하여 해당 fibonacci(n)에 해당하는 값이 필요할 경우 미리 저장한 값을 담고 있는 배열에서 꺼내와 활용할 수 있습니다.

 

메모이제이션으로 구현한 피보나치 수열

# memoization
def fibonacci(n, dp):
    if dp[n]:
        return dp[n]
    if n <= 1:
        return n
    dp[n] = fibonacci(n-2, dp) + fibonacci(n-1, dp)
    return dp[n]

 

타뷸레이션으로 구현한 피보나치 수열

# tabulation
def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]

 

References

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

https://www.youtube.com/watch?v=FmXZG7D8nS4&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98