[CS기초] 다이나믹 프로그래밍(DP, Dynamic Programming)

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)이란?

다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘입니다. 중복되는 계산을 줄여 효율적으로 문제를 해결할 수 있는데요. 곧 하위 문제(subproblem)의 해(solution)를 별도의 저장 공간(DP 테이블)에 미리 기록하고, 이를 재사용함으로써 연산 속도를 획기적으로 향상시킵니다. 이러한 이유로 흔히 ‘똑똑한 재귀’라고도 부릅니다.

 

DP가 빠른 이유는, 한번 계산한 값을 다시 반복적으로 계산하지 않고 미리 저장된 값을 불러오기 때문입니다. 즉, 이미 f(4)나 f(5)와 같이 계산한 결과가 있다면 다시 계산하지 않고 DP 테이블에서 바로 가져오는 것입니다.

 

특히 최대값, 최소값을 구하는 최적화 문제에서는 새로운 결과가 기존에 기록된 결과보다 더 좋은 값(더 크거나 더 작은 값)을 가지는 경우, 이를 기존 결과와 비교해 대체하며 테이블을 갱신하기도 합니다.

 

 

다이나믹 프로그래밍(DP)을 푸는 과정

(1) DP 테이블 정의하기

DP 테이블에 무엇을 저장할지(기억할지) 정의하는 과정입니다. 초보자에게 가장 어렵게 느껴지는 부분으로, 특별한 공식이나 방법론이 따로 존재하지 않기 때문입니다. 주로 문제를 많이 풀면서 경험적으로 감을 잡아야 합니다.

단순히 하나의 상태값만을 저장하는 1차원 DP 테이블을 만들 수도 있지만, 문제에서 요구하는 조건이나 상태가 여러 개라면 2차원 이상의 DP 테이블을 구성하기도 합니다.

(2) 점화식 찾기

DP 테이블에 기록된 항들 간의 관계를 나타내는 점화식을 세우는 과정입니다. 쉽게 말해 n번째 항의 값이 이전 항들(n-1번째 항, n-2번째 항 등)의 값과 어떤 관계성을 갖고 있는지 패턴을 찾아야 합니다.

 

대표적인 예시로, 피보나치 수열은 점화식이

와 같이 표현됩니다.

(3) 초깃값 설정

점화식을 세운 후 DP 테이블을 채우기 위해서는 초깃값이 필요합니다. 초깃값은 일반적으로 문제 자체의 조건에서 주어지거나, 점화식을 처음으로 적용할 때 반드시 필요한 최소한의 값입니다.

 

예를 들어, 피보나치 수열은 문제에서 f(1)=1, f(2)=1 같은 초깃값을 미리 제공합니다.

(4) 테이블 채우기 및 답 찾기

점화식과 초깃값이 모두 준비되었다면 이제 DP 테이블을 순서대로 채우면 됩니다. 테이블을 완성한 후, 최종적으로 문제에서 요구하는 값을 DP 테이블을 통해 찾으면 됩니다.

 

 

Top-Down과 Bottom-Up의 차이

사실 DP 문제를 실제로 구현하는 방식에는 크게 두 가지로 나뉩니다. 바로 Top-Down(상향식)과 Bottom-up(하향식)입니다. 위에서는 DP 테이블을 채우는 Bottom-Up방식으로 다이나믹 프로그래밍을 푸는 과정을 설명했는데요. 이것 말고도 Top-Down이라는 방식으로도 동일하게 문제를 풀 수 있습니다. 둘 다 중복 계산을 피하기 위해 이전 값을 재사용한다는 공통점을 가지지만, 문제를 접근하는 순서와 방식에서 차이가 있습니다.

 

Top-Down 방식 (재귀 + 메모이제이션)

• 큰 문제를 먼저 해결하려 하며, 그 과정에서 작은 문제를 재귀적으로 호출합니다.
• 하위 문제의 결과는 메모이제이션(Memoiation) 기법을 이용해 저장하고 재사용합니다.
• 재귀 기반이기 때문에 코드가 직관적이지만, 함수 호출 스택이 깊어질 경우 스택 오버플로우가 발생할 수 있습니다.

# 피보나치 수열 - Top-Down 방식
def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

 

Bottom-Up 방식 (반복문 + DP 테이블)

• 가장 작은 문제부터 시작해서, 점점 더 큰 문제를 해결해 나갑니다.
• 반복문을 이용해 DP 테이블을 차례로 채워나가므로, 재귀 호출이 없습니다.
• 불필요한 하위 문제까지 계산하는 경우도 있어, 비효율적인 계산이 포함될 수도 있습니다.

# 피보나치 수열 - Bottom-Up 방식
def fib(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

 

두 방식 비교 정리

항목	Top-Down	Bottom-Up
접근 방식	큰 문제부터 재귀적으로 접근	작은 문제부터 순차적으로 접근
구현 형태	재귀 함수 + 메모이제이션	반복문 + DP 테이블
장점	구현이 직관적이고 이해하기 쉬움	함수 호출이 없어 성능 안정적
단점	스택 오버플로우 위험성, 느릴 수 있음	불필요한 계산이 발생할 수 있음
추천 상황	상태나 조건 분기가 복잡할 때	상태 전이가 명확하고 단순할 때