동적 계획법 (DP) - 기본 개념 및 피보나치 수열 예제

동적 계획법(Dynamic Programming, DP)은 문제를 작은 부분 문제로 나누어 해결하고 그 결과를 저장하여, 동일한 문제를 다시 해결할 필요 없이 빠르게 결과를 얻는 최적화 기법입니다. 동적 계획법은 복잡한 문제를 효율적으로 해결할 수 있는 알고리즘 설계 기법으로, 많은 경우 시간 복잡도를 획기적으로 줄여줍니다. 이번 글에서는 동적 계획법의 기본 개념을 설명하고, 피보나치 수열을 예제로 구현해 보겠습니다.

동적 계획법의 기본 개념

동적 계획법은 문제를 해결하기 위해 다음과 같은 두 가지 중요한 개념을 사용합니다:

1. 최적 부분 구조 (Optimal Substructure): 문제를 작은 부분 문제로 나누어 해결할 수 있는 성질을 말합니다. 즉, 문제의 최적 해가 부분 문제의 최적 해로부터 만들어질 수 있습니다.

2. 중복되는 부분 문제 (Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복하여 나타나는 성질을 말합니다. 동적 계획법은 이러한 중복되는 부분 문제를 해결한 결과를 저장하여 재사용합니다.

동적 계획법은 주로 다음 두 가지 방법으로 구현됩니다:

• 메모이제이션 (Memoization): 재귀적으로 문제를 해결하면서, 해결한 부분 문제의 결과를 저장해두고 필요할 때 재사용하는 방법입니다. 이는 주로 탑다운(Top-down) 방식으로 구현됩니다.
• 타뷸레이션 (Tabulation): 작은 부분 문제부터 차례대로 해결하면서 그 결과를 표에 저장해두고, 최종적으로 전체 문제의 해답을 구하는 방법입니다. 이는 보통 바텀업(Bottom-up) 방식으로 구현됩니다.

피보나치 수열 문제

피보나치 수열은 0과 1로 시작하여, 그 이후의 각 숫자가 이전 두 숫자의 합인 수열입니다. 피보나치 수열의 첫 몇 항은 다음과 같습니다: 0, 1, 1, 2, 3, 5, 8, 13, ...

피보나치 수열의 점화식은 다음과 같습니다:

• ( F(0) = 0 )
• ( F(1) = 1 )
• ( F(n) = F(n-1) + F(n-2) ) (( n \geq 2 ))

이제 피보나치 수열을 동적 계획법을 사용하여 Java와 C 언어로 구현해보겠습니다.

Java로 구현한 피보나치 수열 (메모이제이션 사용)

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoization {
    private Map<Integer, Long> memo = new HashMap<>();

    public long fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        FibonacciMemoization fib = new FibonacciMemoization();
        int n = 50;
        System.out.println("Fibonacci(" + n + ") = " + fib.fibonacci(n));
    }
}

위 Java 코드에서는 HashMap을 사용하여 이미 계산한 피보나치 수의 값을 저장합니다. 이를 통해 중복 계산을 방지하고 효율성을 높였습니다. 예를 들어, fibonacci(50)을 계산할 때, 메모이제이션 덕분에 각 부분 문제를 한 번씩만 계산하게 됩니다.

C로 구현한 피보나치 수열 (타뷸레이션 사용)

#include <stdio.h>

long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    long long fib[n + 1];
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n = 50;
    printf("Fibonacci(%d) = %lld\n", n, fibonacci(n));
    return 0;
}

위 C 코드에서는 배열 fib를 사용하여 각 피보나치 수를 저장합니다. 작은 값부터 차례로 계산하면서 저장해두기 때문에 중복 계산이 발생하지 않으며, 계산 속도가 매우 빨라집니다. 이를 타뷸레이션 방식이라고 합니다.

시간 복잡도 비교

• 재귀적 구현 (단순 재귀): 피보나치 수열을 단순 재귀로 구현하면 시간 복잡도가 ( O(2^n) )이 됩니다. 이는 매우 비효율적인 방법입니다.
• 메모이제이션을 사용한 재귀적 구현: 메모이제이션을 사용하면 각 부분 문제를 한 번씩만 계산하므로 시간 복잡도는 ( O(n) )이 됩니다.
• 타뷸레이션을 사용한 구현: 타뷸레이션 방식 역시 모든 부분 문제를 한 번씩만 계산하므로 시간 복잡도는 ( O(n) )이 됩니다.

결론

동적 계획법은 문제를 작은 부분 문제로 나누고, 그 결과를 저장하여 효율적으로 문제를 해결하는 강력한 기법입니다. 피보나치 수열은 동적 계획법의 기본 개념을 설명하기에 좋은 예제입니다. 메모이제이션과 타뷸레이션을 통해 어떻게 중복 계산을 줄이고 성능을 향상시킬 수 있는지 확인할 수 있었습니다.

동적 계획법은 피보나치 수열뿐만 아니라 다양한 문제에 적용될 수 있습니다. 예를 들어, 최단 경로 문제, 배낭 문제, 문자열 유사도 계산 등 여러 분야에서 활용됩니다. 이러한 문제들도 동일한 원리로 해결할 수 있으므로, 동적 계획법의 개념을 잘 이해하고 활용할 수 있다면 많은 알고리즘 문제를 효율적으로 해결할 수 있을 것입니다.