알고리즘 DP ( Dynamic Programming)

알고리즘 DP ( Dynamic Programming ) 코딩테스트 대비

DP란?

큰 문제를 작은 문제로 나누어 푸는 문제. 분할정복과의 차이점은 작은 부분문제들이 반복되는 것을 이용해 풀어나가는 방법입니다.

DP 방법

풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다.

이러한 과정을 메모이제이션(Memoization)이라 한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2]  의 공식에 의해 진행되는 수들의 나열이다.

분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.

D[6] = D[5] + D[4] = D[4] + D[3] + D[3] + 1 = D[3] + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1+ 1 + 1 + 1 + 1

D[6] 을 구하는 과정에서 D[4], D[3] 이 반복적으로 계산되는 것을 볼 수 있다. 

 

다이나믹프로그래밍으로 구하는 과정을 살펴보면 다음과 같다.

D[3] = 1 + 1 = 2

D[4] = 2 + 1 = 3

D[5] = 3 + 2 = 5

D[6] = 3 + 5 = 8

두 방법을 비교 해봤을때 후자가 훨씬 간결한 것을 알 수 있다. 

타일 채우기 ( DP 유형 문제 ) 백준 2133번 

DP 알고리즘을 통해 풀 수 있는 문제.

문제: 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구해보자.

입력: 첫째 줄에 N (1부터 30) 이 주어진다.

출력: 첫째 줄에 경우의 수를 출력한다

예시( 입력:2, 출력:3)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] dp = new int[n + 1];

        int answer = 0;
        if (n % 2 == 1) {
            answer = 0;
        } else {
            dp[0] = 1;
            dp[2] = 3;

            for (int i = 4; i <= n; i += 2) {
                dp[i] = dp[i - 2] * dp[2];
                for (int j = i - 4; j >= 0; j -= 2) {
                    dp[i] += dp[j] * 2;
                }
            }

            answer = dp[n];
        }

        System.out.println(answer);
        sc.close();
    }
}