[WEEK04] 동적 프로그래밍 (DP)

동적 프로그래밍(DP)이란?

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 푸는 최적화 기법이다. 중복되는 부분 문제(subproblem)의 해결 결과를 저장하고 재사용하여 연산을 줄이는 것이 핵심이다.

 

여기서 프로그래밍은 계획법을 의미한다. 즉, 동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리해 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.

왜 동적 프로그래밍이 필요한가?

DP는 다음과 같은 상황에서 유용하다:

• 중복되는 계산을 줄이기 위해: 동일한 부분 문제를 여러 번 풀지 않고 한 번 해결한 값을 저장하여 성능을 향상시킨다.
• 재귀 방식의 비효율성 극복: 단순한 재귀 방식은 중복 호출로 인해 지수 시간 복잡도를 가질 수 있지만, DP를 활용하면 이를 줄일 수 있다.
• 최적 부분 구조(Optimal Substructure)를 가지는 문제 해결: 문제를 작은 단위로 쪼개어 해결할 수 있는 경우 DP를 적용하면 효율적인 풀이가 가능하다.

동적 프로그래밍의 핵심 개념

중복 부분 문제(Overlapping Subproblems)

문제를 작은 하위 문제로 나누었을 때, 동일한 하위 문제가 여러 번 반복해서 등장하는 경우 DP를 적용할 수 있다.

# 재귀 (비효율적인 방법)
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

위 코드는 중복된 부분 문제를 여러 번 계산하여 비효율적이다.

메모이제이션(Memoization)과 탑다운 방식

메모이제이션은 이미 계산된 결과를 저장하여 중복 연산을 방지하는 기법이다.

# 메모이제이션을 활용한 피보나치 (Top-down DP)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

타뷸레이션(Tabulation)과 바텀업 방식

타뷸레이션은 작은 문제부터 차례대로 해결하면서 결과를 저장하는 방식이다.

# 바텀업 방식 (Bottom-up DP)
def fib_bottom_up(n):
    if n <= 1:
        return 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가 활용되는 대표적인 문제

• 피보나치 수열
• 정수 삼각형
• 동전 거스름돈 문제
• 배낭 문제(Knapsack Problem)
• 최장 공통 부분 수열(LCS)
• 최단 경로 문제 (플로이드-워셜 알고리즘 등)

최장 공통 부분 수열(LCS: Longest Common Subsequence)

두 개의 문자열이 주어졌을 때, 두 문자열에서 순서를 유지하며 가장 긴 공통 부분 문자열을 찾는 문제다.

# 특정 자리가 가리키는 행과 열의 문자열값을 비교해
# 값이 같으면 테이블의 대각선 왼쪽 위의 값에 1을 더한 값을 저장한다.
DP[i][j] = DP[i-1][j-1] + 1

# 비교한 값이 다르면 테이블 왼쪽과 위쪽 값 중 큰 값을 선택해 저장한다.
DP[i][j] = max(DP[i-1][i], DP[i][j-1])

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))  # 출력: 4

배낭 문제(Knapsack Problem)

무게 제한이 있는 배낭에 최대 가치를 가지는 아이템을 선택하는 문제다.

def knapsack(W, wt, val, n):
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][W]

# 테스트
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapsack(W, wt, val, n))  # 출력: 220

정리

DP는 복잡한 문제를 효율적으로 해결할 수 있는 강력한 기법입니다. 문제를 해결할 때 중복되는 부분 문제가 있는지, 최적 부분 구조를 만족하는지를 고려하여 DP를 적용할 수 있다.

 

앞으로 DP 문제를 접할 때는 재귀 → 메모이제이션 → 바텀업 방식으로 변환하는 연습을 해보는 것이 좋을 것이다.