[필수 알고리즘] 동적계획법 DP (Dynamic Programming) 이해

동적계획법 DP (Dynamic Programming)

동적 계획법은 프로그래밍 대회 문제에 자주 출현하는 알고리즘 기법 중 하나이며,

프로그램이 실행되는 도중, 실행에 필요한 메모리를 기억하여 할당하는 기법을 의미한다.

 

:  큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법

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

 

중복되는 부분 문제

피보나치 수열을 예시로 코딩하려고 한다.

점화식이 F(n) = F(n-1) + F(n-2)이기 때문에 단순 재귀 함수로 구현된다.

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

일반 피보나치 수열

이러한 피보나치 수열과 같은 중복되는 부분 문제 알고리즘은  N이 작은 함수 호출로 갈수록 그 호출의 횟수가 점점 증가한다.

fib(4)의 값을 구하기 위해 fib(4) = fib(3) + fib(2), 즉 fib(3)와 fib(2)의 값을 알아야 한다. 

fib(3)의 값을 알아내려면 fib(2)+fib(1) 값을 다시 계산을 해야하는 구조가 돼버린다.

이런 식으로 기하급수적으로 늘어나는 호출 횟수 때문에 fib(N)을 구하는 데는 O(2^n) 시간 복잡도가 발생한다.

 

이렇게 중복되는 부분 문제의 비효율을 어떻게 줄일 수 있을까? 

이 전 목차에서 설명한 기억 하여 푸는 기법 (dp)를 활용하여 해결하는 방식으로

 O(N) 시간복잡도가 발생하며 효율적으로 풀 수 있다.

 

DP 알고리즘 기법 활용

DP가 동작하는 방법은 Memoizaition과 Tabulation이 있다. 

1. Memoizaition, Top-down(하향식)

- 중복되는 계산은 한 번만 계산하는 재귀 방식

- 작은 값부터 캐시에 값을 채워나가는 방식

 

 

2. Tabulation, Bottom-up(상향식)

- 답을 구하기 위한 모든 계산을 Table 방식으로 저장하는 for문 방식

- 계산된 값을 캐시에서 꺼내는 방식

 

DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.

 

두 방식의 장단점은 for문과 재귀의 차이로,

 Memoizaition은 재귀 방식이기 때문에 너무 많이 사용하면 call stack이 쌓이고 과부하로 오류를 발생할 가능성이 있지만 위에서부터 계산하는 Top-Down 방식이기 때문에 필요 없는 계산은 하지 않아도 된다. 

 

Tabulation 은 반복문으로 계산하는 Bottom-Up 방식은 과부하로 인한 오류가 생길 일이 없지만 필요 없는 것까지도 계산하게 된다는 단점이다.

 

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

작은 값부터 캐시에 값을 채워나가는 방식

피보나치 함수에서는 먼저 dp [n]을 계산한 적이 있는지 확인하고, 계산한적이 있다면 추가 재귀 호출 없이 그 값을 바로 리턴해 버린다. 이렇게 하면 한 번 계산했던 값은 두 번 다시 계산할 필요가 없으므로, f(N)을 구하는 데 O(N)의 시간만이 필요하다.

 

Tabulation 반복문을 이용한 피보나치수열 알고리즘

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

(for문으로 값을 채움)

이 코드는 재귀 호출 없이 반복문을 통해 구한 알고리즘이다.
이번에는 N보다 작은 피보나치 항의 값들만 정확히 알고 있다면 f(N)을 구하는 데도 문제가 없다는 점을 이용하여 f(2)부터 f(N)까지의 값을 차례대로 구한다.

이렇게 반복문을 사용하는 것 역시 O(N)의 시간복잡도가 걸린다. 한 가지 손해가 있다면, 그냥 구했을 때보다 공간복잡도가 늘어났다는 것인데, 원래는 별도의 메모리가 필요 없었지만 이제는 각 항의 값을 기억하고 있어야 하니까 O(N)의 메모리가 필요하다.

 

DP를 활용하기 적합한 문제

1. 최적 부분 구조(Optimal Substructure)
   • 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
     • 해당 문제를 분할정복 알고리즘과 비슷하다고 생각하여 아래 목차로 정리했다.
2. 중복되는 부분 문제(Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

 

 

동적계획법 (DP) VS 분할정복 (Divide and Conquer)

최적 부분 구조는 분할 정복(Divide and conquer) 방식으로 풀 수 있다. DP와 분할 정복은 해당 문제가 최적 부분 구조의 조건을 가질 때 사용할 수 있다. 상위 문제를 작게 하위 문제로 나누어 해결하는 방식으로 처리하면 된다.

 

차이점은 하위 문제의 중복이다.

 

하위 문제가 독립적이지 않고 중복이 되는 경우에는 DP의 방식이 분할정복보다는 더 나은 시간복잡도를 가진다.

왜냐하면 분할정복에서는 동일한 하위 문제는 각각 독립적으로 구성되어 있기 때문에 반복적으로 계산이 되지 않기 때문이다.