동적 계획법(Dynamic Programming, DP)

7.1 DP의 원리와 적용 조건

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제로 분할하고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 설계 기법입니다. 최적화 문제 해결에 주로 사용되며, 다음 조건을 만족해야 합니다:

1. 중복되는 부분 문제 (Overlapping Subproblems):
2. 동일한 부분 문제가 반복적으로 계산됩니다. 예: 피보나치 수열에서 fib(n-1)과 fib(n-2)가 중복 호출됨.
3. 최적 부분 구조 (Optimal Substructure):
4. 전체 문제의 최적해가 부분 문제의 최적해로 구성됩니다. 예: 최단 경로 문제에서 A→C의 최단 경로는 A→B + B→C입니다.

DP 접근 방법:

• Top-down (Memoization): 재귀 + 메모이제이션 (필요한 부분 문제만 계산).
• Bottom-up (Tabulation): 반복문 + 테이블 (작은 문제부터 순차적으로 계산).

 

7.2 메모이제이션(Memoization) vs. 타뷸레이션(Tabulation)

특징 메모이제이션 (Top-down) 타뷸레이션 (Bottom-up)

접근 방식	재귀 호출로 문제 분할	반복문으로 작은 문제부터 해결
계산 순서	필요한 부분 문제만 계산 (Lazy Evaluation)	모든 부분 문제를 순차 계산
저장 구조	사전(Dict) 또는 배열에 캐싱	테이블(배열)에 저장
공간 복잡도	일반적으로 더 적음	모든 부분 문제 저장 → 더 큼
코드 가독성	재귀적 구조로 직관적	반복문으로 복잡할 수 있음
예시	피보나치 수열 (재귀 + 메모)	피보나치 수열 (반복문 + 배열)

 

7.3 대표 문제 및 실습

1. 피보나치 수열

문제: n번째 피보나치 수를 구하시오.

해결:

• 메모이제이션 (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] print(fib(10)) *# 55*
• 타뷸레이션 (Bottom-up):
• def fib(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] print(fib(10)) *# 55*

2. 0-1 배낭 문제 (Knapsack)

문제: 최대 용량 W의 배낭에 N개 물건을 넣어 최대 가치를 구하시오.

해결:

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(W+1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
    return dp[n][W]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(5, weights, values))  *# 7 (물건 0과 1 선택)*

3. 최장 증가 부분 수열 (LIS)

문제: 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하시오.

해결:

def lis(arr):
    n = len(arr)
    dp = [1] * n  *# dp[i]: arr[i]로 끝나는 LIS 길이*
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))  *# 5 ([10, 22, 33, 50, 60])*

4. 계단 오르기

문제: 1계단 또는 2계단씩 오를 때 N번째 계단까지 오르는 방법의 수.

해결:

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

print(climb_stairs(3))  *# 3 (1+1+1, 1+2, 2+1)*

 

 

DP는 부분 문제의 결과를 저장해 중복 계산을 제거하여 효율성을 극대화합니다.

메모이제이션은 재귀적 접근으로 직관적이며, 타뷸레이션은 반복문으로 공간을 효율적으로 사용할 수 있습니다.