D.P. 동적계획법

모든 알고리즘 문제들은 완전탐색을 이용해도 정답 도출이 가능하지만 비효율적인 연산과 시간을 생략하고 답을 효율적으로 도출하기 위해 여러 알고리즘을 사용한다.

 

동적계획법

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써, 최종적으로 복잡한 문제의 답을 구하는 방법이다.

 

핵심이론

원리와 구현 방식

1. 큰 문제를 작은(부분) 문제로 나눌 수 있어야 함
2. 작은(부분) 문제들이 반복돼 나타나고 사용되며 그들의 결괏값은 항상 같아야함
3. 모든 작은(부분) 문제들은 한번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용
   이를 메모이제이션 이라고 함(시간복잡도 측면에서 유리)
4. DP는 탑-다운, 바텀-업 방식으로 구현가능함

대표문제

피보나치수열

<공식>
D[N] = D[N-1] + D[N-2]
N번째 수열 = N-1번째 수열 + N-2번째 수열

 

ex) 1 1 2 3 5 = D[5] = D[4] + D[3] = 5 + 3 = 8

 

인과관계

• 5번째 = 4번째 값 + 3번째 값
• 4번째 = 3번째 값 + 2번째 값
• 3번째 = 2번째 값 + 1번째 값

 

Step 01) 동적 계획법으로 풀 수 있는지 확인

6번째 피보나치 수열은 5번째 피보나치 수열 + 4번째 피보나치 수열이다.

즉, 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 부분문제로 나눌 수 있고 수열의 값은 항상 같기(일정하기) 때문에 DP로 풀수 있다.

 

큰문제 (6번째) = 작은문제(5번째) ,  작은문제(4번째) 두 작은(부분)문제의 값은 변하지 않고 일정하다.

 

Step 02) 점화식 도출

점화식을 세울 때는 논리적으로 전체 문제를 나눈 뒤, 전체 문제와 부분 문제간의 인과관계(조합의 논리적 관점)를 파악하는 훈련이 필요 (인과관계 파악에는 개인차가 있을 수 있음)

이러한 인과관계 파악 능력은 다양한 실전 문제 경험으로 터득된다.

 

피보나치 수열 공식 자체가 점화식 이므로 피보나치 수열 공식을 점화식으로 사용한다

D[i] = D[i-1] + D[i-2]

 

큰 문제가 있으면 작은(부분)문제가 해결되었다고 가정하고 이 부분문제로 큰 문제를 해결하려면 어떤 인과관계가 있을까

피보나치 수열의 6번째 수열에 대해서 생각해보면

1~5번째 까지 이미 구해져있다고 가정하고 구해진 값들로 어떻게해야 결과값인 6번째 수열을 도출할 수 있을지에 대한 인과관계는 구해진 값들을 기준으로 규칙성을 찾아보면 6번째 = 5번째 + 4번째 라는 규칙이 있다.

이것을 일반화 하게 되면 각 상수들을 N으로 치환하여

6은 N

5는 N-1

4는 N-2 로 변경하여

D[N] = D[N-1] + D[N-2]라는 점화식을 도출해 낼 수 있다.

 

Step 03) 메모이제이션 원리 이해

메모이제이션이란 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산 하지 않고 DP테이블의 값을 재이용 하는것을 말함

 

위에서 2번째와 3번째 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고 이때 DP테이블에 저장된다.

이렇게 저장된 2번째, 3번째에 해당하는 부분문제의 값들은 나중에 2번째 3번째 수열 값이 필요할 때 재연산을 통해 구하지 않고 바로 값을 추출한다.

이렇게 되면 불필요한 연산, 탐색 과정 생략으로 인해 시간복잡도 측면에서 유익하다.

 

Step 04) 탑-다운 구현 방식 이해

위에서부터 문제를 파악해 내려오는 방식으로 주로 재귀함수 형태로 코드를 구현한다.

public class TopDown {

    static int[] D; // DP테이블
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt()
        D = new int[n+1];
        for (int i = 0; i <= n; i++) {
        	D[i] = -1; // 모든 값 초기화 (-1의 경우 계산한적 없는 값)
        }
        D[0] = 0; D[1] = 1;
        fibo(n);
        System.out.println(D[n])
    }
    
    static int fibo(int n) {
    	if (D[n] != -1)
        	return D[n] // 계산한적 있는 부분문제라면 재계산 하지 않고 리턴
        return D[n] = fibo(n-2) + fibo(n-1) // 재귀호출 및 메모이제이션(DP테이블에 구한값 저장)
    }
}

 

Step 05) 바텀-업 구현 방식 이해

가장 작은 부분문제 부터 문제를 해결하면서 점점 큰 문제로 확장하는 방식으로 주로 반복문 형태로 코드를 구현한다.

public class TopDown {

    static int[] D; // DP테이블
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt()
        D = new int[n+1];
        for (int i = 0; i <= n; i++) {
        	D[i] = -1; // 모든 값 초기화 (-1의 경우 계산한적 없는 값)
        }
        D[0] = 0; 
        D[1] = 1;
        for (int i = 2; i <= n; i++) { // 0과 1의 값이 주어졌다는 전제로 범위를 2부터 시작
        	D[i] = D[i-1] + D[i-2];
        }
        System.out.println(D[n])
    }
   
}

두 방식 중 좀더 안전한 방식은 바텀-업 방식이다.

탑-다운 방식은 재귀함수의 형태로 구현돼 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러 발생 가능성이 존재한다.

하지만 실제 코딩테스트에서 이부분까지 고려해야 하는 난이도는 잘 나오지 않는다.

오히려 본인이 구현한 함수에 버그가 있을 확률이 더 높을 것이다.

이 부분을 제외하면 두 방식의 차이점은 거의 없으므로 자신에게 좀더 편한 방식이나, 문제 (재기횟수파악) 에 따라 두 방식중 1개를 선택해 사용하면 된다.