동적 계획법 DP

📍 동적 계획법 DP 이란?

: Dynamic Programming으로,
하나의 큰 문제를 작은 문제로 나누어 해결하는 방식이다.

공간복잡도를 늘리는 대신, 시간복잡도는 줄이는 방식이다.

1. DP 문제 조건

• 최적 부분 구조(Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며, 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.

• 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다.

2. DP 구현

(1) 하향식 Top-Down
: 메모이제이션(Memoization) 기법을 사용하여 문제를 해결하기 위해 재귀적으로 부분 문제를 해결하며, 각 부분 문제의 결과를 저장해두어 재사용한다.

단점: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있으며, 메모리 사용이 많을 수 있다.

public class Fibonacci { // 피보나치 수열
    static int[] dp = new int[1000];
    static int fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(dp[n] != 0) return dp[n];
        dp[n] = fibonacci(n - 2) + fibonacci(n - 1);
        return dp[n];
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(fibonacci(N));
    }
}

(2) 상향식 bottom - up
: 작은 부분 문제부터 시작하여 점차 큰 문제로 확장해 나가면서 해결한다. 배열에 결과를 저장하여 나중에 사용할 수 있다.

단점: 문제를 처음부터 끝까지 해결해야 하므로 메모리 사용이 많을 수 있다.

public class Fibonacci{ // 피보나치 수열
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];
        dp[1] = 1;
        for(int i = 2;i <= N;i++)
        	dp[i] = dp[i - 1] + dp[i - 2];
        System.out.println(dp[N]);
    }
}