[알고리즘] Dynamic Programming

 피보나치 문제의 예시를 보자. 피보나치의 경우 재귀함수를 이용한 Divide-and-Conquer 방법으로 풀 수도 있지만, 재귀의 방법을 사용하면 모든 호출된 재귀함수들이 fib(1)에서부터 계산해나가야 하기 때문에 수행시간이 길다.

//재귀를 사용한 피보나치, Top-down
public int fibInRecursive(int n) {
    if(n<=1)
        return n;
    else
        return fibInRecursive(n-1)+fibInRecursive(n-2);
}

//반복 알고리즘을 사용한 피보나치, Bottom-up
public int fibInIterative(int input) {
    int[] fib = new int[input+1];

    fib[0]=0;
    if(input>=1) {
        fib[1]=1;
        for(int i=2; i<input+1; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
    }
    return fib[input];
}

따라서 배열을 이용하여 이전 피보나치 값을 저장하여 불필요한 중복 계산을 줄일 수 있는데, 이때 나누어진 부분들 사이에 상관관계가 존재하게 된다. 이러한 방법을 동적 계획법이라고 한다.

 

문제 예시

BOJ 1932) 정수 사각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제

 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

풀이

 처음에는 삼각형에서 왼쪽 아래 혹은 오른쪽 아래로 진행하므로 백트래킹을 이용한 dfs로 풀면 되겠다고 생각해서 코드를 짰다.

- DFS를 이용한 구현

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        // 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열.
        int size = sc.nextInt();
        int[][] arr = new int[size+1][size+1];
        int[] best = new int[1];

        for(int i=1; i<=size; i++) {
            for(int j=1; j<=i; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        dfs(arr, 1, 1, size, 0, best);
        System.out.println(best[0]);
    }

    public static void dfs(int[][] arr, int i, int j, int size, int sum, int[] best) {
        sum += arr[i][j];
        if(i==size) {
            if (best[0] < sum)
                best[0] = sum;
            return;
        }
        dfs(arr, i+1, j, size, sum, best);
        dfs(arr, i+1, j+1, size, sum, best);
    }

}

하지만 이 경우 삼각형의 depth가 500인 이 문제에서는 풀 수 없는 문제가 된다. 왜냐하면 depth가 100정도만 되어도 dfs를 이용한 백트래킹으로는 무한대에 가까운 시간이 걸리기 때문이다. 이런 경우에 동적 계획법을 사용하여 이전 단계의 값에 더해서 best값을 도출하는 식으로 문제를 해결하자.

- dp를 사용한 구현

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        // 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열.
        int size = sc.nextInt();
        int[][] arr = new int[size+1][size+1];
        int[][] sum = new int[size+1][size+1];
        int max;

        for(int i=1; i<=size; i++) {
            for (int j = 1; j <= i; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

		//첫 값 대입
        sum[1][1] = arr[1][1];
        max = arr[1][1];
        for (int i = 2; i <= size; i++) {
            for (int j = 1; j <= i; j++) {
            	//삼각형의 양쪽 끝에 있는 경우 선택지가 1개밖에 없다.
                if(j==1)
                    sum[i][j] = sum[i-1][j] + arr[i][j];
                else if(j==i)
                    sum[i][j] = sum[i-1][j-1] + arr[i][j];
                else
                    sum[i][j] = Math.max(sum[i - 1][j] + arr[i][j], sum[i - 1][j - 1] + arr[i][j]);

                if(i==size && max<sum[i][j])
                    max = sum[i][j];
            }
        }

        System.out.println(max);
    }
}

매 depth마다 이전 depth의 값만 참고하면 되므로 실행시간이 단축된다.

 

동적 계획법

 Divide-and-Conquer의 방법과 유사하지만, 단순히 큰 문제를 작은 문제들로 나누어 푸는(하향식 접근, Top-down) divide-and-conquer와 다르게 나누어진 부분들 사이에 상관관계가 존재하며, 작은 부분의 문제를 해결해서 큰 문제를 해결하는 방법으로(상향식 접근, Bottom-up), 중복계산을 방지한다는 점에서 차이가 있다.

 물론 top-down의 재귀함수를 이용한 순환꼴로도 문제들이 중복계산되지 않도록 결과값을 별도의 배열에 저장해놓는(메모이제이션)등의 방법을 이용하여 동적 계획법을 적용할 수도 있다. (결국 점화식도 저장값을 사용하지 않는다면 순환함수를 이용하는 재귀꼴로 풀어야 하니까)

 어쨋든 그 구현 방법과는 상관없이, 동적계획법은 모든 작은 문제들은 한번씩만 풀도록 하며, 그 작은 문제들의 풀이를 따로 저장해 놓는다. 다른 큰 문제를 풀때 작은 문제의 풀이가 필요하면 저장해놓은 풀이를 사용한다.

(Q+작은 문제와 큰 문제를 푸는 방법이 동일해야한다.)

두 방법 모두 동일한 결과를 도출해 낼 수 있지만, 앞서 이야기했듯 재귀함수의 특성상 불필요한 반복이 시행될 수 있고, 소스의 가독성이 저하될 수 있다.