동적 프로그래밍

동적 프로그래밍(Dynamic programming)

정의

복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘 설계 기법으로, 하위 문제의 답을 저장하여 중복 계산을 방지합니다.

동작 원리

메모이제이션(memoization) 또는 테이블 방식을 사영하여 이미 계산된 결과를 재사용합니다.

# 피보나치 수열 - 메모이제이션 방식
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# 피보나치 수열 - 테이블 방식
def fibonacci_table(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]

# 배낭 문제 (Knapsack Problem)
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],  # 현재 물건을 선택하지 않는 경우
                    dp[i-1][w-weights[i-1]] + values[i-1]  # 선택하는 경우
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# 예제
print(f"피보나치 30번째 (메모): {fibonacci_memo(30)}")
print(f"피보나치 30번째 (테이블): {fibonacci_table(30)}")

# 배낭 문제 예제
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
capacity = 5
print(f"배낭 문제 최댓값: {knapsack(weights, values, capacity)}")