동적 프로그래밍(Dynamic Programming)은 중복되는 연산을 피하고 메모이제이션(Memoization)을 통해 연산 속도를 향상시키는 알고리즘 설계 기법입니다. 이 기법은 최적화 문제나 조합 최적화 문제 같은 문제들을 효율적으로 해결하는 데 널리 사용됩니다. 이번 포스트에서는 동적 프로그래밍을 활용한 두 가지 예제인 피보나치 수열과 최장 공통 부분 수열에 대해 알아보겠습니다.

피보나치 수열

피보나치 수열은 이전 두 개의 항을 더해서 다음 항을 만들어내는 수열입니다. 예를 들어, 0과 1부터 시작하는 피보나치 수열은 다음과 같습니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

피보나치 수열을 동적 프로그래밍을 활용하여 구현하면 아래와 같습니다:

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]

위에 작성한 fibonacci 함수는 피보나치 수열의 n번째 항을 구하는 함수입니다. 이 함수는 동적 프로그래밍의 기본 개념을 활용해서 중복 계산을 피하고 계산한 값을 메모하여 재활용합니다. 따라서, n이 큰 경우에도 효율적으로 계산할 수 있습니다.

최장 공통 부분 수열

최장 공통 부분 수열(Longest Common Subsequence)은 두 개의 문자열이 주어졌을 때, 두 문자열에 공통으로 나타나는 가장 긴 수열을 찾는 문제입니다. 이 문제는 동적 프로그래밍을 활용하면 효율적으로 해결할 수 있습니다.

아래는 두 문자열의 최장 공통 부분 수열을 찾는 함수의 예시입니다:

def lcs(str1, str2):
    m = len(str1)
    n = len(str2)

    # 동적 프로그래밍 테이블 생성
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 테이블 갱신
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[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]

위에 작성한 lcs 함수는 두 문자열 str1과 str2의 최장 공통 부분 수열의 길이를 반환하는 함수입니다. 이 함수는 동적 프로그래밍의 개념을 활용하여 효율적으로 문제를 해결합니다. 만약, 두 문자열의 길이가 크다고 해도 동적 프로그래밍을 활용하여 빠르게 최장 공통 부분 수열을 찾을 수 있습니다.

결론

이번 포스트에서는 동적 프로그래밍을 활용한 피보나치 수열과 최장 공통 부분 수열에 대해 알아보았습니다. 동적 프로그래밍은 중복 계산을 피하고 메모이제이션을 통해 연산 속도를 향상시키는 효율적인 알고리즘 설계 기법입니다. 이러한 동적 프로그래밍은 다양한 최적화 문제와 조합 최적화 문제를 해결하는 데 유용하게 사용될 수 있습니다.