동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 나누어 풀고, 그 결과를 저장하여 재활용하는 기법입니다. 이를 통해 문제의 시간복잡도를 크게 줄일 수 있습니다.

동적 프로그래밍은 보통 다음과 같은 단계로 진행됩니다:

1. 큰 문제를 작은 하위 문제들로 나눕니다.
2. 작은 하위 문제들을 푸는 방법을 찾습니다.
3. 작은 하위 문제들을 푼 결과를 이용하여 큰 문제를 해결합니다.

이번 포스트에서는 동적 프로그래밍을 활용하여 효율적으로 문제를 해결하는 방법과 그에 대한 예제를 소개하겠습니다.

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

피보나치 수열은 이전 두 개의 수를 더한 값을 다음에 추가하는 형태로 이루어집니다. 예를 들어, 처음 두 숫자는 0과 1이며, 그 다음 숫자는 1입니다. 이 과정을 반복하면 다음과 같은 수열이 생성됩니다: 0, 1, 1, 2, 3, 5, 8, …

우리의 목표는 피보나치 수열의 n번째 숫자를 계산하는 것입니다.

일반적인 방법으로는 재귀를 이용하여 피보나치 함수를 구현할 수 있습니다. 하지만 이 방법은 중복 계산이 발생하여 비효율적입니다.

동적 프로그래밍을 활용하여 중복 계산을 피하고 피보나치 수열을 효율적으로 계산하는 코드를 살펴보겠습니다.

def fibonacci(n):
    # 기저 사례: n이 0 또는 1인 경우
    if n <= 1:
        return n
    
    # 이미 계산한 값이 있는 경우, 바로 반환
    if memo[n] is not None:
        return memo[n]
    
    # 계산한 값이 없는 경우, 피보나치 수열 계산
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

# 피보나치 수열의 10번째 숫자 출력
n = 10
memo = [None] * (n+1)  # 계산한 값을 저장하기 위한 메모리
print(fibonacci(n))

위 코드에서는 memo라는 리스트를 이용하여 이미 계산한 값을 저장합니다. 이를 통해 중복 계산을 피하고 피보나치 수열을 효율적으로 계산할 수 있습니다.

2. 배낭 문제 해결하기

배낭 문제는 무게와 가치가 있는 아이템들을 배낭에 담을 때, 배낭에 담을 수 있는 아이템의 최대 가치를 구하는 문제입니다.

예를 들어, 배낭의 최대 용량이 10이고, 아이템들이 다음과 같이 주어졌다고 가정해봅시다:

이 경우, 배낭에 담을 수 있는 아이템의 최대 가치는 300입니다.

이 문제를 동적 프로그래밍을 활용하여 효율적으로 풀 수 있는데, 다음과 같은 방법을 사용할 수 있습니다.

1. 배낭의 크기에 따라 가능한 모든 조합을 확인합니다.
2. 각 아이템을 추가할 때, 해당 아이템이 배낭의 용량을 초과하지 않는 경우에만 가치를 누적하여 저장합니다.
3. 최종적으로 저장된 값이 배낭에 담을 수 있는 아이템의 최대 가치입니다.

def knapsack(capacity, weights, values, n):
    # 기저 사례: 배낭의 크기가 0일 때
    if capacity == 0 or n == 0:
        return 0

    # 이미 계산한 값이 있는 경우, 바로 반환
    if memo[n][capacity] is not None:
        return memo[n][capacity]

    # 아이템을 추가하지 않는 경우
    if weights[n-1] > capacity:
        memo[n][capacity] = knapsack(capacity, weights, values, n-1)
    else:
        # 아이템을 추가하는 경우와 추가하지 않는 경우 중 더 큰 값을 저장
        memo[n][capacity] = max(
            values[n-1] + knapsack(capacity-weights[n-1], weights, values, n-1),
            knapsack(capacity, weights, values, n-1)
        )
    return memo[n][capacity]

# 배낭의 최대 용량과 아이템들의 정보
capacity = 10
weights = [3, 5, 2, 1]
values = [100, 250, 150, 50]

n = len(weights)
memo = [[None for _ in range(capacity+1)] for _ in range(n+1)]  # 계산한 값을 저장하기 위한 메모리
print(knapsack(capacity, weights, values, n))

위 코드에서는 memo라는 2차원 리스트를 이용하여 이미 계산한 값을 저장합니다. 이를 통해 중복 계산을 피하고 배낭 문제를 효율적으로 해결할 수 있습니다.

결론

동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 분해하여 풀고, 그 결과를 저장하여 재활용하는 기법입니다. 예제로 피보나치 수열 계산과 배낭 문제를 효율적으로 해결하는 방법을 살펴보았습니다.

동적 프로그래밍은 다양한 문제에 적용될 수 있으며, 효율적인 문제 해결을 위한 강력한 방법론입니다. 사용하는 프로그래밍 언어에 상관없이 동적 프로그래밍을 활용하여 문제 해결 전략을 개발하고, 효율적인 알고리즘을 구현할 수 있습니다.