동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 하위 문제로 나눠서 푸는 방법입니다. 이를 통해 중복된 계산을 피하고 효율적으로 문제를 해결할 수 있습니다. Python은 동적 프로그래밍에 매우 적합한 언어이며, 다양한 문제에 적용할 수 있습니다.

이 글에서는 동적 프로그래밍을 활용하여 문제를 해결하는 몇 가지 예시를 살펴보겠습니다.

1. 피보나치 수열

피보나치 수열은 이전 두 항을 더하여 다음 항을 만들어내는 수열입니다. 동적 프로그래밍을 사용하지 않으면 중복된 계산을 반복하게 되어 효율성이 떨어지지만, 동적 프로그래밍을 활용해 이 문제를 효율적으로 해결할 수 있습니다.

def fibonacci(n):
    dp = [0, 1]  # 초기값
    
    for i in range(2, n + 1):
        dp.append(dp[i-1] + dp[i-2])  # 현재 항 = 이전 두 항의 합
    
    return dp[n]

위의 코드는 bottom-up 방식으로 피보나치 수열을 구하는 함수입니다. dp 리스트를 사용해 이미 계산된 값을 저장하고, 필요한 값만 계산하여 저장한 뒤 참조하여 중복된 계산을 방지합니다.

2. 최장 증가 부분 수열

주어진 수열에서 부분 수열 중에서 가장 길고 순차적으로 증가하는 부분 수열을 찾는 문제입니다. 동적 프로그래밍을 사용하여 이 문제를 해결할 수 있습니다.

def longest_increasing_subsequence(nums):
    dp = [1] * len(nums)  # 초기값
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)  # 현재 길이 = 이전 길이 중에서 가장 큰 값 + 1
    
    return max(dp)

위의 코드는 bottom-up 방식으로 최장 증가 부분 수열의 길이를 구하는 함수입니다. dp 리스트를 사용해 각 인덱스에 최장 증가 부분 수열의 길이를 저장하고, 이전 인덱스의 값과 현재 값을 비교하여 갱신합니다.

3. 배낭 문제

주어진 무게와 가치가 있는 일련의 물건들 중에서 배낭의 최대 무게를 초과하지 않으면서 최대 가치를 담을 수 있는 문제입니다. 동적 프로그래밍을 활용하여 이 문제를 해결할 수 있습니다.

def knapsack(weights, values, capacity):
    dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]  # 초기값
    
    for i in range(1, len(weights) + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(values[i-1] + dp[i-1][j-weights[i-1]], dp[i-1][j])  # 현재 가치 = 이전 가치 중에서 가장 큰 값
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[len(weights)][capacity]

위의 코드는 bottom-up 방식으로 배낭 문제를 해결하는 함수입니다. 2차원 배열 dp를 사용해 현재까지 고려한 물건들의 가치의 최대값을 저장하고, 이전 단계의 값과 현재 물건의 가치를 비교하여 갱신합니다.

이처럼 동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나눠서 해결하는 방법입니다. Python을 사용하여 동적 프로그래밍을 구현하면 효율적인 문제 해결을 할 수 있습니다. 동적 프로그래밍을 활용한 다른 예시도 많이 있으니, 관심 있는 분야에서 응용해보시기 바랍니다.