Python을 이용한 동적 계획법(Dynamic Programming)의 기초와 응용

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 방법은 하위 문제의 해답을 저장함으로써 중복 계산을 방지하고, 전체 문제를 효율적으로 해결합니다. Python은 이러한 기법을 구현하기에 매우 적합한 언어입니다. 이 글에서는 Python을 활용한 동적 계획법의 기본 원리와 몇 가지 구현 예를 살펴보겠습니다.

 

피보나치 수열

피보나치 수열은 동적 계획법을 소개할 때 자주 사용되는 예제입니다. 각 피보나치 수는 바로 앞의 두 피보나치 수의 합으로 정의됩니다. 간단한 재귀 방식은 많은 중복 계산을 발생시키기 때문에, 동적 계획법을 사용하여 효율적으로 계산할 수 있습니다:

 

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # 10번째 피보나치 수를 계산

 

 

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

두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제입니다. LCS는 다음과 같이 Python을 사용하여 동적 계획법으로 구현할 수 있습니다:

 

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

X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))  # 출력: 4 (GTAB)

 

 

반응형

 

 

 

0-1 배낭 문제 (0-1 Knapsack Problem)

이 문제는 주어진 무게 한도 내에서 아이템을 선택하여 가치의 총합을 최대화하는 방법을 찾는 문제입니다. 각 아이템은 한 번만 선택하거나 선택하지 않을 수 있습니다. 다음은 0-1 배낭 문제를 동적 계획법으로 해결하는 Python 코드입니다:

 

def knapsack(W, wt, val, n):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapsack(W, wt, val, n))  # 출력: 220

 

 

동적 계획법은 이처럼 문제를 작은 부분으로 나누어 해결하는 방식으로, 많은 최적화 문제에서 효율적인 해결책을 제공합니다. Python에서의 구현은 비교적 간단하며, 메모이제이션과 테이블을 활용하여 시간 복잡도를 크게 줄일 수 있습니다. 이와 같은 방법으로 복잡한 문제를 시스템적으로 접근하고 해결할 수 있습니다.