동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복되는 계산을 피하고 효율적으로 문제를 해결할 수 있습니다. 이번 포스트에서는 Python에서 동적 프로그래밍을 활용하여 문제를 해결하는 방법에 대해 알아보겠습니다.

1. 피보나치 수열 계산하기

피보나치 수열은 이전의 두 수를 더하여 현재의 수를 만들어내는 수열입니다. 다음은 동적 프로그래밍을 사용하여 피보나치 수열을 계산하는 예시 코드입니다.

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. 최장 증가 부분 수열(LIS) 찾기

최장 증가 부분 수열(Longest Increasing Subsequence)은 주어진 수열에서 연속되지 않은 증가하는 원소들의 최대 길이를 찾는 문제입니다. 동적 프로그래밍을 활용하여 최장 증가 부분 수열을 찾는 예시 코드는 다음과 같습니다.

def lis(arr):
    n = len(arr)
    lis = [1] * n  # 각 원소가 마지막 원소인 경우의 최장 부분 수열 길이
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))  # 결과: 5

위 코드에서 lis 리스트는 각 원소가 마지막 원소인 부분 수열의 최대 길이를 저장하는 역할을 합니다. 이를 통해 현재 원소와 이전 원소들을 비교하면서 최장 부분 수열의 길이를 계산합니다.

동적 프로그래밍은 복잡도가 높은 문제를 효율적으로 해결하기 위한 중요한 기법입니다. Python과 같은 동적 언어에서는 이를 활용하여 보다 간편하고 빠르게 문제를 해결할 수 있습니다.

위 예시들은 동적 프로그래밍의 일부에 불과하며, 동적 프로그래밍은 다양한 문제에 적용될 수 있습니다. 따라서 각 문제의 특성에 맞는 동적 프로그래밍 알고리즘을 설계하고 구현하는 능력을 키우는 것이 중요합니다.