[알고리즘] 동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming, DP)이란?

---

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -- 위키피디아

동적 계획법의 특징

• 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장(memoization)하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
• 최다 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 

동적 계획법 조건

아래 조건을 만족할 때 동적 계획법을 사용할 수 있다.

1. 작은 문제가 반복하여 일어난다.
2. 같은 문제는 구할 때마다 정답이 같다.

탐욕법(Greedy Algorithm) vs 동적 계획법(Dynamic Programming)

탐욕법

• 최적의 해가 보장되지 않는다.
• 동적 계획법에 비해 속도가 빠르다.

동적 계획법

• 최적의 해가 보장된다.
• "가능한 모든 방법을 고려"하기 때문에 탐욕법 보다 속도가 느리다.

Bottom Up vs Top Down

Bottom UP

• 반복문을 사용하여 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식
• 재귀적으로 함수를 호출하지 않기 때문에 메모리 사용량을 줄일 수 있다. 
• 메모이제이션, 동적 계획법

Top Down

• 재귀 호출을 사용하여 큰 문제를 먼저 방문 후, 작은 문제를 호출하여 답을 찾는 방식
• 재귀적으로 함수를 호출하기 때문에 메모리 비용이 많이 든다. (재귀는 콜스택에 쌓이기 때문에 메모리 비용이 높다.)

동적 계획법 예시

---

대표적인 예시로 피보나치 수열 문제가 있다. 피보나치 수열의 알고리즘은 N이 작은 함수 호출로 갈수록 그 호출의 횟수가 점점 증가한다.

이미지 출처: https://miro.medium.com/max/925/1*svQ784qk1hvBE3iz7VGGgQ.jpeg

재귀를 사용하는 경우

• 점화식: f(N) = f(N-1) + F(N-2)
• 재귀를 사용할 경우, 같은 함수를 계속해서 중복 호출을 하게 된다.  따라서 f(N)을 구하는데 있어서 시간 복잡도는 O(2^n)이다.
• Top-down 방식

public class Fibonacci{
	static int fibonacci(int n){
    	if(n == 0) return 0;
        if(n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(fibonacci(N));
    }
}

동적 계획법을 사용하는 경우

동작 순서는 아래와 같다. 

1. 이전에 dp[n]의 값을 계산한적이 있는지 확인한다.
2. 계산한 적이 없다면 dp[n]에 값을 저장한다.
3. 계산한 적이 있어서 dp[n]에 값이 저장되어있다면 해당 값을 사용한다.

• 한번 계산했던 값을 재사용하기 때문에  f(N)을 구하는데 있어서 시간 복잡도는 O(N)이다.
• Bottom-up 방식

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));
    }
}