[파이썬 자료구조] 동적 계획법

동적 계획법이란?

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 푸는 알고리즘 기법 중 하나입니다. DP는 부분 문제의 결과 값을 저장해놓고 재활용하여 전체 문제를 해결하는 방식으로 동작합니다.

동적 계획법의 조건

DP는 크게 2가지 조건을 만족해야 합니다.

1. 작은 부분 문제들이 반복되어 나타나는 구조여야 합니다.
2. 한 부분 문제에서의 정답이 다른 부분 문제에서의 정답을 결정하는 데 영향을 미쳐서는 안 됩니다.

동적 계획법의 절차

DP 알고리즘은 일반적으로 다음과 같이 세가지 절차를 따릅니다.

1. 주어진 문제를 작은 부분 문제로 분할합니다.
2. 부분 문제의 해결을 위해 이전 단계에서 구한 값을 저장하고 재귀로써 문제를 해결합니다.
3. 모든 부분 문제를 해결하여 전체 문제의 해답을 구합니다.

Memoization 기법

Memoization은 동적 계획법의 한 종류로, 계산 결과를 저장하여 재사용하는 기법입니다. 메모리를 이용해 중복 계산을 피하는 방법입니다. 재귀함수에 제격입니다. 일전에 재귀함수의 문제에 대해 포스팅 했었는데 이런 부분을 개선시킬 수 있습니다. 하지만 메모리를 많이 쓰는 만큼 모든 것을 Memoization으로 해결하려고 하면 안되고 신중히 사용하셔야 합니다.

사용방법

딕셔너리를 활용하면 재귀함수의 중복계산을 피할 수 있습니다. 함수를 호출할 때 함수의 인자를 키(key)로 하고 결과를 값(value)으로 하는 딕셔너리를 만들어서 함수의 결과를 저장합니다. 이후 함수가 호출될 때마다 딕셔너리를 참조하여 결과를 가져오는 방식으로 중복 계산을 피합니다.

동적계획법 구현해보기

동적계획법의 대표적인 예제로는 피보나치, LCS(Longest Common Subsequence), Knapsapck Problem이 있습니다.
모든 예제들은 재귀함수로도 구현이 가능하지만 숫자가 커지면 계산량이 엄청나게 많아지는 단점이 있습니다.
이를 보완하는 방식으로 동적계획법을 생각하면 좋을 것 같습니다.

피보나치 수열

피보나치 수열은 재귀함수로도 할 수 있는데 동적계획법으로 하면 훨씬 빠르게 출력할 수 있습니다.

def fibonacci(n):
    memo = [0] * (n+1)  # 결과를 저장할 리스트
    memo[0] = 0  # 초기값
    memo[1] = 1  # 초기값

    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]  # 이전 결과 이용
    return memo[n]

print(fibonacci(10))  # 55 출력

위 코드에서 memo 리스트는 이미 계산한 결과를 저장해두기 위해 사용됩니다. 초기값으로 memo[0] = 0과 memo[1] = 1을 설정합니다. 그리고 2부터 n까지 반복문을 돌면서 memo[i]에 memo[i-1]과 memo[i-2]의 합을 저장합니다. 마지막으로 memo[n]을 반환합니다.

이렇게 하면 n이 커져도 계산 속도가 빨라집니다. 예를 들어, fibonacci(100)을 실행하면 결과를 바로 얻을 수 있습니다. 반면에 일반적인 재귀 함수를 이용한 피보나치 수열 계산 방법은 n이 커질수록 계산 시간이 지수적으로 증가합니다.

LCS(Longest common sequence)

LCS는 두 문자열에서 공통으로 나타나는 가장 긴 부분 문자열을 찾는 문제입니다. 예를 들어, "ABCDGH"와 "AEDFHR" 두 문자열의 LCS는 "ADH"입니다. 이 문제는 두 문자열의 길이를 n이라고 할 때, 지수 시간 복잡도를 가지는 재귀 함수로 구현하면, 상당히 비효율적입니다. 따라서, 동적 계획법을 사용하여 부분 문제를 구성하고, 부분 문제의 해결 방법을 저장하고 재사용함으로써 중복 계산을 피합니다.

def lcs(str1, str2):
    m = len(str1)
    n = len(str2)
    table = [[0 for j in range(n+1)] for i in range(m+1)] # m+1 x n+1 크기의 테이블 생성
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]: # 두 문자가 같은 경우
                table[i][j] = table[i-1][j-1] + 1
            else: # 두 문자가 다른 경우
                table[i][j] = max(table[i-1][j], table[i][j-1])
    return table[m][n]

동적 계획법을 사용하지 않게 되면 가능한 모든 부분 수열을 생성하고 거기서 최장 공통 부분을 찾게 됩니다. 너무 비효율적이고 시간복잡도가 지수로 측정되어 사용하는 시간이 기하급수로 늘어납니다.

마치며

동적계획법에 대해 알아보았습니다. 메모리의 한계를 개선하기에 좋은 방법인 것 같습니다. 유용하게 활용하시기 바랍니다.

 

함께 보면 좋은 글

[파이썬 알고리즘] 재귀용법(recursive call, 재귀호출)