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

이번 주 백준 문제 유형이 자료구조 수업 때 배우지 않은 DP이기에 이를 공부한 바탕으로 DP를 정리해보려 한다.

두괄식으로 먼저 DP를 정의한 문구들을 보고 가자.

DP란 ?

→ *메모이제이션(Memoization) 기법을 이용하며 '하나의 문제는 단 한 번만' 풀도록 하게 하는 알고리즘

* 계산했던 것을 메모리 공간에 기억해 두고, 같은 식을 써야한다면 앞에서 기억한 것을 재사용하는 기법

분할 정복 기법과 DP의 차이점

분할 정복 : 큰 문제를 작은 부분 문제로 나누고, 그 하위 문제를 독립적으로 해결하고 이를 합쳐서 원래 문제를 해결함

	동적 계획법(DP)	분할 정복
중복되는 문제	O	X
메모이제이션	O (중복 문제의 결과를 저장하고 재활용함)	X
문제 분할 방식	문제의 크기와 형태에 따라 다름	동일한 크기의 하위 문제로 나눔
예시	피보나치 수열, 최단 경로 문제, 배낭 문제..	퀵 정렬, 병합 정렬, 큰 수의 곱셈..

 

즉, 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 존재함. (퀵 정렬, 병합 정렬.. 제외)

• 정렬은 왜 위 단점에 해당되지 않는가?

-> 정렬의 경우, 피봇이 옮겨지며 나누어지는 부분을 "이전 문제와 같은 경우로 취급하는 것이 아닌 새로운 문제로 받아들이기 때문"

f(6) = f(5) + f(4)

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

이처럼 같은 계산이 여러 번 반복된다.

• 피보나치수열의 점화식

level 0 = 1

level 1 = 2

level 2 = 4

level 3 = 8

… 2^n 개씩 나누어진다.

일반적인 재귀함수로 피보나치 수열 계산

public class Main {
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 1;
        return dp(x-1) + dp(x-2);
    }
    public static void main(String[] args) {
        System.out.println(dp(10));
    }
}

동일한 문제를 계속 사용하게 되는데, 그때마다 또다시 계산하고 있다.

만약 10이 아닌, 46이 들어간다면? 50은 ?

2^46, 2^50..

수행시간 = O(2^n) = 완전 구데기

2^50의 경우 페비바이트로, 10의 15승이다.

DP를 사용하여 풀기

먼저 DP를 쓰려면 ?

문제만 보고 어떻게 DP인지 알아내는가

입력 x가 return dfs(x-1) + dfs(x-2) + dfs(x-2);에서 1이 될때까지 계속 카운팅 되고 있음. ⇒ 비효율적

1. 큰 문제를 작은 문제로 나눌 때(분할 정복)
2. 작은 문제에서 구한 정답이 큰 문제에서도 동일하게 쓰일 때

두가지 조건을 충족해야 DP를 적용할 수 있다.

DP 문제 풀이를 위한 2가지의 접근 방법

1. 탑다운 방식(Top - down) = 순환적 알고리즘
2. 바텀업 방식(Bottom - up) = 반복적 알고리즘  

탑다운 방식

public class Main {
    static int[] cache = new int[100];
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 1;
        if(cache[x] != 0) return cache[x];
        return cache[x] = dp(x-1) + dp(x-2);
    }
    public static void main(String[] args) {
        System.out.println(dp(46));
    }
}

 

일반적인 재귀함수 코드와 달리 계산했던 값을 저장하는 배열이 생긴 모습을 볼 수 있다.

바텀업 방식

public class Main {
    static int[] cache = new int[100];
    public static int dp(int x){
        cache[0] = 0;
        cache[1] = cache[2] = 1;
        for(int i= 2; i<= x; i++){
            cache[i] = cache[i-1] + cache[i-2];
        }
        return cache[x];
    }
    public static void main(String[] args) {
        System.out.println(dp(10));
    }
}

이처럼 코드를 작성하면, d[3] = 2, d[4] = 3… 이렇게 한 번 계산해두면, d[1] + d[2] 를 하지 않고 d[3] = 2 를 바로 기억하여 또다시 계산할 필요가 없음

더 내려가지 않고, 기억해 둔 값을 쓰면 됨.

수행시간 = O(n) = 높이에 비례

백준 11727번 (2×n 타일링 2)

11727번을 이해하기 위한 사진, https://girawhale.tistory.com/34

별도의 문제에 대한 설명은 하지 않고 위 사진으로 설명을 마치겠습니다.

상기 문제의 경우 DFS를 이용하여 풀 수도 있다.

• DFS 방식

import java.util.Scanner;

public class Main {
    public static int dfs(int x){
        if(x<=1) return 1;
        return dfs(x-1) + dfs(x-2) + dfs(x-2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int val = sc.nextInt();

        System.out.println(dfs(val));
    }
}

범위가 (1 ≤ n ≤ 1000) 이기에 1000을 넣을 시 왕왕 오래 걸림.

 

• DP 방식

import java.util.Scanner;

public class Main {
    static int[] d = new int[1001];

    public static int dp(int x) {
        if (x <= 1) return 1;
        if (d[x] != 0) return d[x];

        d[x] = (dp(x - 1) + 2 * dp(x - 2)) % 10007;
        return d[x];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int val = sc.nextInt();

        System.out.println(dp(val));
    }
}