동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 작은 단위로 나누어 해결하는 과정을 의미합니다. 이 방법론은 중복되는 계산을 피할 수 있도록 하여 효율적인 문제 해결을 가능하게 합니다. 동적 프로그래밍은 대표적으로 메모이제이션(Memoization) 기법을 사용하는데, 계산한 결과를 저장하여 나중에 다시 사용함으로써 중복 계산을 피하고 시간을 단축할 수 있습니다.

동적 프로그래밍은 다양한 문제 해결에 활용될 수 있습니다. 이번 포스트에서는 동적 프로그래밍을 활용한 문제 해결 전략을 파이썬으로 구현하는 예시를 살펴보겠습니다.

1. 피보나치 수열

피보나치 수열은 이전 두 항을 더한 값을 현재 항으로 하는 수열로, 다음과 같이 정의됩니다.

fib(n) = fib(n-1) + fib(n-2)

이 문제를 동적 프로그래밍으로 해결하기 위해서는 이전 계산 결과를 저장하고, 중복 계산을 피해야 합니다. 아래는 피보나치 수열을 동적 프로그래밍으로 구현한 예시 코드입니다.

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

print(fibonacci(10))  # 55

위 코드에서는 fib 리스트를 활용하여 이전 계산 결과를 저장하고, 이를 활용하여 현재 항을 계산합니다. 이를 통해 중복 계산을 피하고, 피보나치 수열을 효과적으로 계산할 수 있습니다.

2. 배낭 문제

배낭 문제는 제한된 용량의 배낭에 최적의 가치를 가진 물건들을 담는 문제입니다. 각 물건은 무게와 가치를 가지고 있으며, 배낭의 용량을 초과하지 않는 물건들을 선택하여 최대 가치를 구해야 합니다.

배낭 문제를 동적 프로그래밍으로 해결하기 위해서는 가능한 모든 물건의 조합을 고려하여 최적의 해를 구해야 합니다. 아래는 배낭 문제를 동적 프로그래밍으로 구현한 예시 코드입니다.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity+1) for _ in range(n+1)]  # 다이나믹 프로그래밍 테이블
    for i in range(1, n+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[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 10

위 코드에서는 dp 테이블을 활용하여 가능한 모든 물건의 조합에 대해 최적의 가치를 저장합니다. 이를 통해 배낭 문제를 효과적으로 해결할 수 있습니다.

3. 최장 증가 부분 수열

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다. 이를 동적 프로그래밍으로 해결하기 위해서는 이전 계산 결과를 활용하여 현재 계산을 수행해야 합니다.

아래는 최장 증가 부분 수열 문제를 동적 프로그래밍으로 구현한 예시 코드입니다.

def lis(nums):
    n = len(nums)
    dp = [1] * n  # 다이나믹 프로그래밍 테이블
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

nums = [3, 2, 5, 1, 6, 4, 9]
print(lis(nums))  # 4

위 코드에서는 dp 리스트를 활용하여 각 위치에서의 최장 증가 부분 수열의 길이를 저장합니다. 이를 통해 최장 증가 부분 수열 문제를 효과적으로 해결할 수 있습니다.

결론

동적 프로그래밍은 복잡한 문제를 작은 문제로 분할하여 해결하는 방식으로, 중복 계산을 방지하여 효율적으로 문제를 해결합니다. 피보나치 수열, 배낭 문제, 최장 증가 부분 수열 등 다양한 문제에 동적 프로그래밍을 적용할 수 있으며, 이를 파이썬으로 간단하게 구현할 수 있습니다. 동적 프로그래밍을 활용하면 효율적인 문제 해결 전략을 구현할 수 있으므로, 코딩 테스트나 알고리즘 문제 풀이에 활용해보시기 바랍니다.