다이나믹 프로그래밍 ( Dynamic Programing ) 이란?

다이나믹 프로그래밍 (이하 동적 계획법) 은

어떤 값을 구할 때, 이전에 계산된 값을 재사용하는 걸 말해요.

엄밀히 말하면, 다이나믹 프로그래밍은 DFS 나 BFS 처럼 알고리즘이 아니라 문제를 해결하는 패러다임에 가까워요.

• 어떤 문제를 풀기 위해서 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 값을 재활용

위와 같은 방식의 알고리즘을 총칭해요.

다이나믹 프로그래밍 사용조건

동적계획법을 사용해서 문제를 해결하기 위해서는 2가지 조건이 만족되어야 해요.

• 1 ) Overlapping Subprombles ( 겹치는 부분 문제 )
• 2 ) Optimal Substructure ( 최적 부분 구조 )

1) Overlapping Subproblems (겹치는 부분 문제)

이 조건은 같은 작은 문제가 여러 번 반복해서 등장한다는 것을 의미해요. 즉, 한번 계산한 값을 다시 계산하지 않고 저장해두었다가, 필요할 때 재사용하면 효율적으로 문제를 해결할 수 있어요.

예를 들어, 피보나치 수열을 생각해볼게요.

fib(5) = fib(4) + fib(3)
        = (fib(3) + fib(2)) + (fib(2) + fib(1))

위처럼 fib(3)과 fib(2)가 중복되어 계산되고 있어요. 이걸 그대로 계산하면 지수 시간 복잡도가 들지만, 한 번 계산한 결과를 메모이제이션(Memoization) 기법으로 저장해두면 훨씬 빠르게 구할 수 있어요.

2) Optimal Substructure (최적 부분 구조)

이 조건은 큰 문제의 최적해가 작은 문제의 최적해로부터 구성될 수 있어야 한다는 뜻이에요.

즉, 문제를 부분 문제로 나눌 수 있고, 각 부분 문제의 최선의 해결 방법이 전체 문제의 최선의 해결 방법이 된다면 동적 계획법을 적용할 수 있어요.

다시 피보나치 예시를 들면, fib(5)를 구하려면 fib(4)와 fib(3)을 알면 되죠.
그리고 fib(4)와 fib(3) 역시 피보나치 수열의 정의에 따라 최적의 값으로부터 구해져야 하니까, 이 조건을 만족하는 거예요.

다이나믹 프로그래밍의 2가지 방식

동적 계획법은 크게 상향식(Bottom-Up) 과 하향식(Top-Down) 두 가지 방식으로 구현할 수 있어요.

1. 하향식 (Top-Down) - 메모이제이션

• 재귀 + 메모이제이션
• 필요한 값만 계산함
• 구현이 간단함

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

2. 상향식 (Bottom-Up) - 타뷸레이션

• 반복문 사용
• 작은 문제부터 차례대로 해결
• 메모리 사용량이 예측 가능함

def fib(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

마무리

이처럼 복잡해 보이지만, 큰 문제를 작게 쪼개고 그 해답을 재사용할 수 있는 문제에 DP를 적용할 수 있어요.

정리하자면, 다이나믹 프로그래밍은 다음과 같은 상황에서 사용할 수 있어요:

• 같은 계산을 반복하고 있다면 → 중복되는 부분 문제
• 문제를 나눠서 풀 수 있고, 각 작은 문제의 최선이 전체 최선이라면 → 최적 부분 구조

이 두 가지 조건이 만족된다면,
탐색 알고리즘보다 훨씬 빠르게 문제를 해결할 수 있는 강력한 도구가 돼요.

우리 모두 DP 의 개념에 대해서 이해하고 좀 더 즐거운 알고리즘 풀이 시작해요 ^^~