동적 프로그래밍(Dynamic Programming)은 다양한 최적화 문제를 해결하기 위해 사용되는 효율적인 알고리즘 기법입니다. 최적화 문제는 주어진 조건과 제약을 만족하면서 가장 좋은 값을 찾는 문제를 말합니다. 이러한 문제들은 순차적인 결정을 통해 해결되며, 동적 프로그래밍은 이러한 결정들 사이에 중복이 발생하는 문제를 해결하여 계산 효율성을 크게 향상시킵니다.

Python은 동적 프로그래밍 알고리즘을 구현하기에 적합한 언어이며, 다양한 최적화 문제를 효과적으로 해결할 수 있습니다. 이번 포스트에서는 동적 프로그래밍을 활용하여 최적화 문제를 해결하는 예제를 다루어보겠습니다.

1. 피보나치 수열

피보나치 수열은 각 항이 바로 앞의 두 항의 합인 수열입니다. 동적 프로그래밍을 사용하여 피보나치 수열을 구하는 코드는 다음과 같습니다.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        fib = [0, 1]
        for i in range(2, n + 1):
            fib.append(fib[i - 1] + fib[i - 2])
        return fib[n]

# 피보나치 수열의 10번째 항 출력
print(fibonacci(10))

위의 코드에서는 재귀적인 방법 대신 반복문을 사용하여 더욱 효율적으로 피보나치 수열을 계산합니다. 이러한 방식을 바텀업(Bottom-up) 방식이라고도 합니다. 배열 fib에 중간 결과를 저장하고 참조하여 계산을 진행함으로써 중복 계산을 피할 수 있습니다.

2. 배낭 문제

배낭 문제(Knapsack Problem)는 주어진 여러 개의 물건들의 가치와 무게가 있을 때, 배낭의 용량을 초과하지 않으면서 최대의 가치를 얻을 수 있도록 물건들을 선택하는 문제입니다. 동적 프로그래밍을 사용하여 배낭 문제를 해결하는 코드는 다음과 같습니다.

def knapsack(items, capacity):
    n = len(items)
    table = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(1, capacity + 1):
            if weight > w:
                table[i][w] = table[i - 1][w]
            else:
                table[i][w] = max(value + table[i - 1][w - weight], table[i - 1][w])
    
    return table[n][capacity]

# 물건의 가치와 무게
items = [(60, 10), (100, 20), (120, 30)]
# 배낭의 용량
capacity = 50

# 최대 가치 출력
print(knapsack(items, capacity))

위의 코드에서는 2차원 배열 table을 생성하여 각 물건을 선택하거나 선택하지 않는 경우의 최대 가치를 저장합니다. 이를 통해 중복 계산을 피하고, 최적해를 찾기 위해 반복문을 활용합니다.

동적 프로그래밍은 다양한 최적화 문제에 적용할 수 있는 강력한 기법입니다. 위의 예제들은 동적 프로그래밍을 활용하여 최적화 문제를 해결하는 방법을 보여줍니다. Python의 간결한 문법과 함께 동적 프로그래밍을 사용하여 다양한 문제를 해결해보세요.