DP(Dynamic Programming)

동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 해결하기 위해 그 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 한 번만 해결하여 그 결과를 저장하고 재사용하는 방법론입니다. DP는 주로 중복된 계산을 피하고 문제를 효율적으로 해결하기 위해 사용됩니다.

 

동적 계획법의 주요 특징

1. 중복된 계산 제거: 동일한 부분 문제를 여러 번 계산하지 않고, 한 번 계산한 값을 저장해두고 다시 사용합니다.

2. 부분 문제: 큰 문제를 해결하기 위해서는 작은 문제들의 해결이 필요합니다.

3. 최적 부분 구조: 전체 문제의 최적 해결은 부분 문제의 최적 해결을 바탕으로 합니다.

4. 메모리 사용: DP는 계산한 값을 저장하는 테이블(보통 배열이나 리스트)을 사용합니다.

 

동적 계획법의 두 가지 기본 접근 방식

1. 탑다운 방식 (Top-down): 재귀 호출을 이용하여 문제를 풀고, 이미 계산한 값을 메모이제이션 기법을 통해 저장하여 중복 계산을 방지합니다.

2. 바텀업 방식 (Bottom-up): 작은 문제부터 차례대로 해결해 나가며 최종적으로 큰 문제를 해결합니다. 일반적으로 반복문을 사용합니다.

 

예시 문제: 피보나치 수열

피보나치 수열을 구하는 문제는 동적 계획법의 전형적인 예시입니다. 피보나치 수는 이전 두 수의 합으로 정의됩니다. 예를 들어, `fib(n) = fib(n-1) + fib(n-2)`입니다.

 

1. 탑다운 방식 (메모이제이션)

public class Fibonacci {

    // 메모이제이션을 위한 배열
    static int[] memo;
    
    public static int fib(int n) {
        // 이미 계산된 값이 있으면 그 값을 반환
        if (memo[n] != -1) {
            return memo[n];
        }

        // 피보나치 계산
        if (n <= 1) {
            memo[n] = n;
        } else {
            memo[n] = fib(n - 1) + fib(n - 2);
        }

        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10; // 구하고자 하는 피보나치 수

        memo = new int[n + 1]; // 배열 크기 지정

        // 배열 초기화 (값이 계산되지 않았음을 표시하기 위해 -1로 초기화)
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }

        System.out.println(fib(n)); // 55 출력
    }
}

 

2. 바텀업 방식 (반복문)

public class Fibonacci {

    public static int fib(int n) {
        // 0과 1의 피보나치 값은 0과 1
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 피보나치 수를 저장할 변수들
        int a = 0, b = 1, c = 0;

        // 2부터 n까지 반복하면서 피보나치 계산
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }

        return c;
    }

    public static void main(String[] args) {
        int n = 10; // 구하고자 하는 피보나치 수

        System.out.println(fib(n)); // 55 출력
    }
}

 

동적 계획법의 효율성

- 시간 복잡도: 반복문이나 메모이제이션을 사용함으로써 시간 복잡도를 줄일 수 있습니다. 예를 들어, 피보나치 수열의 경우 단순 재귀로는 지수 시간 복잡도가 걸리지만, 동적 계획법을 사용하면 선형 시간 복잡도 O(n)으로 해결할 수 있습니다.

- 공간 복잡도: DP에서는 테이블을 사용하므로 공간을 어느 정도 차지합니다. 그러나 일부 문제에서는 공간 최적화를 통해 1차원 배열만으로도 해결할 수 있습니다.

 

DP 문제 해결 전략

1. 문제를 더 작은 부분 문제로 나눈다.

2. 부분 문제를 해결한 후 그 결과를 저장한다.

3. 중복 계산을 피하기 위해 저장된 값을 재사용한다.

 

동적 계획법은 특히 최적화 문제, 경로 문제, 조합 문제 등에서 효과적으로 사용됩니다.