[알고리즘] DP(Dynamic Programing) 이란

 

다이나믹 프로그래밍(동적 계획법)이란?

다이나믹 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하는 방법이다.

 

이때 작은 하위 문제들의 해결 결과를 저장하고, 중복 계산을 피하여 전체 문제를 효율적으로 해결하는 것이 특징이다.

 

이렇게 하면 지수적인 시간 복잡도를 갖는 재귀적인 해결 방법보다 훨씬 효율적으로 문제를 풀 수 있다.

 

위에 설명이 어렵다면 그냥 과정중에 중복되는 계산이 있다면 자료구조에 저장해서 다음에 중복된 계산이 있을때 저장한 값을 활용해서 연산시간의 이득을 얻는 알고리즘이다. 
이런 구조 때문에 기억하기 알고리즘이라고 불리기도 한다.

 

다이나믹 프로그래밍의 특징

1. 중복 부분 문제 (Overlapping Subproblems): 다이나믹 프로그래밍은 동일한 하위 문제들이 반복해서 해결되는 경우에 효과적이다.  이전에 계산한 결과를 저장해 두면 같은 하위 문제를 다시 계산하지 않아도 되어 시간을 절약할 수 있다.
2. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해가 작은 하위 문제의 최적해로부터 구성될 수 있는 경우에 다이나믹 프로그래밍을 적용할 수 있다. 이때 작은 문제의 해결 결과들을 조합하여 전체 문제의 최적해를 얻을 수 있다.

 

다이나믹 프로그래밍의 예시

다이나믹 프로그래밍은 다양한 문제에 적용될 수 있다.

대표적인 예시

피보나치 수열 계산: 피보나치 수열은 자신의 바로 이전 두 항을 더한 값을 가지는 수열이다.

 

재귀적인 방법으로 피보나치 수열을 계산하면 중복 계산이 많이 발생한다.

 

다이나믹 프로그래밍을 활용하면 중복 계산을 피하고 효율적으로 피보나치 수열을 계산할 수 있다.

위 그림을 보면 f(x)의 연산을 하는데 반복되는 x를 볼 수 있다.

 

모든 경우를 다 계산하면 너무 큰 연산이 예상된다

 

만약 dp를 사용한다면?

 

한번 연산을 수행하면 그 값들을 저장하는 방식이다.

 

 

 

public class FibonacciDP {
    public static int fibonacci(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        int n = 10; // 계산할 피보나치 수열의 인덱스
        int result = fibonacci(n);
        System.out.println("피보나치 수열의 " + n + "번째 항: " + result);
    }
}

 

다이나믹 프로그래밍의 종류

1. 탑다운 방식 (Top-Down Approach): 재귀와 메모이제이션을 활용하여 큰 문제를 작은 문제로 쪼개어 해결합니다. 이때 중복 계산을 피하기 위해 이전에 계산한 결과를 메모이제이션 배열에 저장합니다.
2. 바텀업 방식 (Bottom-Up Approach): 작은 하위 문제부터 시작하여 필요한 중간 결과를 계산하고 이를 조합하여 큰 문제의 해답을 구합니다. 일반적으로 반복문을 활용하여 구현합니다.