동적계획법(DP, Dynamic Programming)

동적계획법(DP, Dynamic Programming) 이란?

---

동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 저장 공간이 계속 필요한 대신 시간복잡도는 O(n)을 가진다.

(출처 : 위키백과)

 

 

 

접근

---

 

• f(a, b) = f(a-1, b) + f(a, b-1) (a, b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0, n) = 1

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a, b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

 

출처 : 나무위키

 

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이때 중복되는 부분 문제에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a, b의 값이 커질수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a, b 값에 대해 f(a, b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참고해보자.

 

 

(a,b)	그냥 계산 시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	5	4
(4,4)	69	16
(6,8)	3002	48
(10,10)	184755	100

 

 

---

예제

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

• 처음 문제를 풀 때는 단순히 완전탐색에 조건을 건 걸면 되겠구나 라고 생각을 해서 DFS로 풀었더니 테스트 케이스는 통과가 됐었다. 하지만 시간초과가 터져버리고 말았다. 다른 풀이가 생각이 안 나서 질문하기를 보면서 팁을 찾았었다.
• 질문하기에서 코드를 봐도 이해가 안가서 프로그래머스에서 제공하는 알고리즘 해설 강의(https://www.youtube.com/watch?v=Mrm1YzgvTQw)를 찾아서 듣고 나서야 이해가 갔다.
• 다음은 테스트 케이스에 대한 풀이 예제이다.

1	2	3	5
5	6	7	8
4	3	2	1

 

1(0 + 1)	2(0 + 2)	3(0 + 3)	5(0 + 5)
10(5 + 5)	11(6 + 5)	12(7 + 5)	11(8 + 3)
16(4 + 12)	15(3 + 12)	13(2 + 11)	13(1 + 12)

 

문제의 제약 사항인 동일한 열의 다음 행으로 진행할 수 없다는 조건을 고려했을 때, 어떤 경로를 진행하던 최댓값은 똑같습니다. 이 문제의 요지는 다음과 같다. 어떤 경로를 진행하던 이전 행의 최댓값에는 영향을 주지 않는다는 것이다. 그렇기 때문에 최댓값을 저장하면서 다음 행으로 진행하면 위와 같이 표가 완성되고 '16'이라는 값이 도출된다.

 

 

소스코드

---

public class EatGround {
    // https://school.programmers.co.kr/learn/courses/30/lessons/12913
    // 땅따먹기

    public int solution(int[][] land) {
        int answer = 0;

        for (int i = 1; i < land.length; i++) {
            land[i][0] += Math.max(land[i - 1][1], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][1] += Math.max(land[i - 1][0], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][2] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][3]));
            land[i][3] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][2]));
        }

        return max(land[land.length - 1]);
    }

    private int max(int[] ints) {
        int sum = 0;
        for (int num : ints) {
            sum = Math.max(sum, num);
        }

        return sum;
    }
}

 

 

번외

---

• 맞는 코드인지는 모르겠지만 처음에 DFS로 풀었던 코드이다.
• 행이 너무 길지 않은 케이스라면 동작할 것 같다.

public class Solution {
    // https://school.programmers.co.kr/learn/courses/30/lessons/12913
    // 땅따먹기

    int answer;
    int[][] land;

    public int solution(int[][] land) {
        this.answer = 0;
        this.land = land;

        dfs(1, 0, land[0][0]);
        dfs(1, 1, land[0][1]);
        dfs(1, 2, land[0][2]);
        dfs(1, 3, land[0][3]);

        return answer;
    }

    public void dfs(int depth, int index, int total) {
        if (depth == land.length) {
            answer = Math.max(total, answer);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (i != index) {
                dfs(depth + 1, i, total + land[depth][i]);
            }
        }
    }
}