Python을 활용한 동적 프로그래밍 기법 소개

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 풀고, 각 하위 문제의 결과를 저장하여 중복 계산을 방지하는 방법입니다. 이러한 방식은 문제를 효율적으로 해결할 수 있게 해 주며, Python은 동적 프로그래밍을 적용하기에 매우 적합한 언어입니다. 여기서는 Python을 사용하여 기본적인 동적 프로그래밍 문제를 해결하는 방법과 그 예제를 소개하겠습니다.

 

피보나치 수열 최적화

앞서 재귀를 이용한 피보나치 수열 구현에서 각 수는 여러 번 계산되어 비효율적이었습니다. 동적 프로그래밍을 사용하면 이 문제를 해결할 수 있습니다. 아래는 피보나치 수열의 n번째 수를 계산하는 DP 방식의 구현입니다:

def fibonacci_dp(n):
    fib_cache = {0: 0, 1: 1}
    for i in range(2, n+1):
        fib_cache[i] = fib_cache[i-1] + fib_cache[i-2]
    return fib_cache[n]

 

 

이 방식은 각 수를 한 번만 계산하고 결과를 fib_cache라는 사전에 저장하여, 필요할 때 다시 계산하지 않고 바로 사용합니다.

 

 

0-1 배낭 문제 (Knapsack Problem)

0-1 배낭 문제는 가방에 넣을 수 있는 물건들의 최대 가치를 계산하는 문제입니다. 물건을 쪼갤 수 없는 경우에 적용되며, 각 물건은 무게와 가치를 가집니다. Python에서 동적 프로그래밍을 사용하여 이를 해결할 수 있습니다:

 

def knapsack(max_weight, weights, values):
    n = len(values)
    dp = [[0] * (max_weight + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, max_weight + 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][max_weight]

 

 

이 코드는 각 물건과 각 가방 무게에 대해 최대 가치를 저장하는 2차원 리스트 dp를 사용합니다. 각 셀의 값은 해당 물건과 무게 조합에서 가능한 최대 가치를 나타냅니다.

 

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

두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 가장 긴 수열을 찾는 LCS 문제 역시 동적 프로그래밍으로 효율적으로 해결할 수 있습니다:

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    L = [[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]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[m][n]

 

 

이 예제에서는 두 입력 문자열의 각 문자 조합에 대한 최장 길이를 저장하여 계산합니다.

 

이와 같이 동적 프로그래밍은 문제의 중복된 부분을 한 번만 계산하고 결과를 재활용함으로써, 계산 시간을 대폭 줄일 수 있습니다. Python의 다양한 자료 구조를 활용하면 이러한 방식의 프로그래밍을 쉽고 효과적으로 구현할 수 있습니다.