동적 계획법(Dynamic Programming)

동적 계획법

동적 계획법은 부분 문제로 분해할 수 있는 최적화, 탐색, 계산 문제를 해결하기 위한 일반적인 방법을 말한다.

 

동적 계획법은 작은 문제 여러 개를 합쳐서 큰 문제를 풀 수 있다. 이 때, 동일한 하위 문제가 반복해서 발생할 수 있다.

 

따라서 동적 계획법을 효율적으로 작성하려면 반복해서 발생하는 하위 문제의 결괏값을 캐싱해 두어야 한다.

 

동적 계획법의 기본 개념을 익히기 위해 피보나치 수열이 자주 사용된다.

 

피보나치 수열

피보나치 수열은 0, 1로 시작하고 그 다음 숫자부터는 이전 두 숫자의 합이다. 따라서 0, 1, 1, 2, 3, 5, 8, ...이 된다.

 

수학적으로 표현하면 다음과 같다.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

코드로 표현하면 다음과 같다.

 

private static Map<Integer, Integer> cache = new HashMap<>();
 
public static int fibonacci(int n) {
    if(n <= 1)
        return n;
    else if(!cache.containsKey(n))
        cache.put(n, fibonacci(n- 2) + fibonacci(n - 1));
    
    return cache.get(n);
}

 

위 코드의 시간 복잡도는 O(n)이고, 공간 복잡도도 O(n)이다.

 

캐시 공간을 최소화하는 것은 동적 계획법에서 중요하므로, 같은 프로그램을 O(1) 공간으로 구해 보자.

 

public static int fibonacci(int n) {
    if(n <= 1)
        return n;
 
    int fMinus2 = 0;
    int fMinus1 = 1;
    
    for(int i=2; i<=n; i++) {
        int f = fMinus2 + fMinus1;
        fMinus2 = fMinus1;
        fMinus1 = f;
    }
 
    return fMinus1;
}
 

앞선 프로그램과 개념적으로는 반대다. 상향식으로 캐시를 반복적으로 채워 공간 복잡도를 줄이고, 캐시를 재사용할 수 있게 한다.

 

동적 계획법을 효율적으로 푸는 핵심은 하나의 문제를 부분 문제로 나누는 방법을 찾는 것이다. 부분 문제는 다음과 같은 특징이 있다.

1. 부분 문제의 해법을 찾으면 원래 문제도 비교적 쉽게 해결할 수 있다.

2. 부분 문제의 해법을 캐시에 저장할 수 있다.

 

최대 부분합 구하기

조금 더 복잡한 문제를 다루어 보자.

 

정수 배열이 주어졌을 때 합이 가장 큰 부분배열을 동적 프로그래밍으로 구하자. 

 

아래 배열에서 합이 최대가 되는 부분배열은 0번~3번 인덱스까지다.

 

모든 부분배열의 합을 구해야 하므로 무식하게 풀면 시간 복잡도가 O(n^3)이 된다. 부분배열의 개수는 n(n-1)/2 이고, 각 부분배열의 합을 구하는 데 O(n)의 시간이 걸리기 때문이다.

 

하지만 O(n)의 공간을 사용해서 모든 k에 대한 S[k] = ∑A[0, k]를 저장할 수 있다면 무식한 방법의 시간 복잡도를 O(n^2)으로 개선할 수 있다. A[i, j]의 합은 S[j] - S[i - 1]이고, S[-1]은 0이 된다.

 

 

이제 동적 계획법으로 문제를 풀어 보자. 부분배열 A[0, n-2]의 해법을 알고 있다고 가정하고 문제를 푸는 것에서 시작하고 싶을 것이다. 그러나 부분배열 A[0, n-2]의 최대부분합을 알고 있다고 하더라도 A[0, n-1]의 해법을 구하는 데 도움이 되지 않는다.

 

i < n-1의 모든 부분배열 A[0, i]에 대해서 가장 작은 부분배열의 합을 알고 있어야 도움이 된다. 이 정보를 알고 있으면 S[n-1]에서 부분배열의 합을 뺀 값 중에 최댓값이 정답이 되기 때문이다.

 

다시 말해 j로 끝나는 최대부분합은 S[j] - min(S[k])가 된다.(k <= j)

배열을 차례대로 순회할 때마다 합이 가장 작은 S[k]를 추적할 수 있으므로 각 인덱스에 대한 최대 부분합을 찾을 수 있다.

 

각 인덱스에서 최대 부분합을 구하는 데 상수시간이 걸리므로 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)이 된다. 모든 배열의 값이 음수일 수도 있고 배열이 비어 있을 수도 있기 때문에, 이런 경우의 입력도 처리할 수 있어야 한다.

 

public static int findMaximumSubarray(List<Integer> A) {
    int minSum = 0, sum = 0, maxSum = 0;
 
    for(int i=0; i<A.size(); i++) {
        sum += A.get(i);
 
        if(sum < minSum)
            minSum = sum;
        
        if(sum - minSum > maxSum)
            maxSum = sum - minSum;
    }
 
    return maxSum;
}

 

동적 계획법 문제를 풀기 전 꼭 알고 있어야 할 내용

문제가 부분 문제와 관련이 있는 경우에는 더더욱 동적 계획법을 고려해 봐야 한다.

 

동적 계획법은 최적화 문제뿐 아니라 개수를 세는 문제, 의사 결정 문제를 푸는 데도 쓸 수 있다. 동일한 계산을 재귀적으로 사용하는 작은 부분 문제들로 전체 문제를 표현할 수 있다면 동적 계획법으로 풀 수 있다.

 

이와 같은 개념으로 보자면, 동적 계획법에는 재귀가 포함된다. 하지만 캐시는 효율성을 위해 상향식, 즉 반복적으로 구축되는 경우가 많다.

 

동적 계획법이 재귀적으로 구현될 때, 캐시는 보통 해시 테이블이나 이진 탐색 트리 같은 동적 자료구조로 구현된다. 반복적으로 구현되는 캐시는 보통 1차원이나 다차원 배열이다.

 

공간을 절약하기 위해 다시 사용하지 않게 될 캐시 공간을 재사용할 수도 있다.

 

가끔은 상향식 동적 계획법보다 재귀가 더 효율적일 때가 있다. 예를 들어 해법을 빨리 찾을 수 있거나 가지치기를 통해 탐색해야 할 부분 문제의 개수를 줄이는 경우다.

 

동적 계획법은 부분 문제에 대한 해법을 결합하여 원래 문제에 대한 해법을 제시한다. 하지만 동적 계획법으로 풀 수 없는 문제도 있다. 예를 들어 중간 도시를 반복해서 경유하지 않고, 도시1에서 도시2까지 가는 가장 긴 경로를 구해야 한다고 하자. 이 경로는 도시3을 통과한다. 이때 도시1에서 도시3으로, 그리고 도시3에서 도시2로 가는 각각의 하위 경로는 문제에서 요구했던 '중간 도시를 반복해서 경유하지 않는 가장 긴 경로'가 아닐 수도 있다.

 

문제 16.1 가능한 개수가 몇 개인지 구하기

응용1: 같은 문제를 O(s)의 공간을 사용해서 풀어 보자.

 

public class Main
{
    public static void main(String[] args)
    {
        System.out.println(getScore(12));
    }
 
    public static int getScore(int n) {
        int[] arr = new int[]{2, 3, 7};
        int[] dp = new int[n+1];
        dp[0] = 1;
 
        for(int i=0; i<=2; i++) {
            int target = arr[i];
            
            for(int j=target; j<=n; j++) {
                dp[j] += dp[j-target];
            }
        }
        
        return dp[n];
    }
}

 

응용2: 최종 점수와 각 게임에서 낼 수 있는 점수가 주어졌을 때, 최종 점수를 만들 수 있는 수열의 개수를 반환하라. 예를 들어 12점을 낼 수 있는 수열은 <2, 2, 2, 3, 3>, <2, 3, 2, 2, 3>, <2, 3, 7>, <7, 3, 2>를 포함해서 총 열여덟 가지다.

 

public class Main
{
    public static void main(String[] args)
    {
        System.out.println(getSequence(12, 0, new int[]{2, 3, 7}));
    }
 
    public static int getSequence(int score, int sum, int[] arr) {
        if(sum > score)
            return 0;
        else if(sum == score)
            return 1;
 
        int num = 0;
        for(int i=0; i<arr.length; i++) {
            num += getSequence(score, sum + arr[i], arr);
        }
 
        return num;
    }
}

 

응용5: 계단을 올라가려고 한다. 한번에 한 칸에서 k칸까지 올라갈 수 있고, n번째 계단에 도달하려고 한다. n과 k가 입력으로 주어졌을 때, n번째 계단에 도달할 수 있는 방법의 개수를 반환하는 프로그램을 작성하라.

 

public class Main
{
    public static void main(String[] args)
    {
        System.out.println(getSequence(4, 0, 2));
    }
 
    public static int getSequence(int n, int sum, int k) {
        if(sum > n)
            return 0;
        else if(sum == n)
            return 1;
 
        int num = 0;
        for(int i=1; i<=k; i++)
            num += getSequence(n, sum + i, k);
 
        return num;
    }
}

 

문제 16.2 레벤슈타인 거리 구하기

철자가 틀린 문자열이 주어졌을 때, 맞춤법 검사기는 사전에서 해당 문자열과 가장 가까운 단어를 반환한다.

 

1965년에 블라디미르 레벤슈타인은 두 단어의 거리를, 철자가 틀린 단어에서 철자가 올바른 단어로 변환하는 데 필요한 최소 편집 횟수라고 정의했다. 여기서 편집이란 문자의 삽입, 삭제, 치환을 말한다.

 

예를 들어 "Saturday"에서 "Sundays"로 변환하려면 첫 번째 'a'와 't'를 삭제하고, 'r'을 'n'으로 치환하고, 마지막에 's'를 삽입해야 하므로, 이 둘 사이의 레벤슈타인 거리는 4가 된다.

 

무식한 방법은 두 번째 문자열과 같은 문자열을 찾을 때까지 첫 번째 문자열과 거리가 1, 2, 3, ...인 모든 문자열을 나열한다.

 

이보다 더 나은 방법은 탐색 도중 '가지치는' 방법이다. 첫 번째 문자열과 두 번째 문자열의 마지막 문자가 같다면 이 문자는 무시해도 된다.

 

a와 b가 각각 문자열 A와 B의 길이라고 했을 때, E(A[0, a-1], B[0, b-1])이 A와 B의 레벤슈타인 거리이다. 여기서 다음과 같은 사실을 알 수 있다.

1. A의 마지막 문자가 B의 마지막 문자와 같다면 E(A[0, a-1], B[0, b-1]) = E(A[0, a-2], B[0, b-2])이다.

2. A의 마지막 문자가 B의 마지막 문자와 다르다면 다음과 같다.

E(A[0, a-1], B[0,b-1])= 1 + min(E(A[0, a-2], B[0,b-2]), E(A[0, a-1], B[0, b-2]), E(A[0, a-2], B[0, b-1]))

 

A에서 B로 변환하는 방법에는 다음 세 가지가 있다.

ㆍA[0, a-2]에서 B[0, b-2]로 변환한 뒤에 A의 마지막 문자를 B의 마지막 문자로 치환하면 된다.

ㆍA[0, a-1]에서 B[0, b-2]로 변환한 뒤에 B의 마지막 문자를 뒤에 추가하면 된다.

ㆍA[0, a-2]에서 B[0, b-1]로 변환한 뒤에 A의 마지막 문자를 삭제하면 된다.

 

코드로 옮기면 다음과 같다. 이 코드의 시간, 공간 복잡도는 모두 O(ab)이다.

 

import java.util.*;
import java.io.*;
 
public class Main
{
    public static void main(String[] args)
    {
        System.out.println(levenshteinDistance("Carthorse", "Orchestra"));
    }
 
    public static int levenshteinDistance(String A, String B) {
        int[][] distanceBetweenPrefixes = new int[A.length()][B.length()];
        for(int[] row: distanceBetweenPrefixes) {
            Arrays.fill(row, -1);
        }
 
        return computeDistanceBetweenPrefixes(A, A.length() - 1, B, B.length() - 1, distanceBetweenPrefixes);
    }
 
    private static int computeDistanceBetweenPrefixes(String A, int A_idx, String B, int B_idx, int[][] distanceBetweenPrefixes) {
        if(A_idx < 0) 
            return B_idx + 1;
        else if(B_idx < 0) 
            return A_idx + 1;
 
        if(distanceBetweenPrefixes[A_idx][B_idx] == -1) {
            if(A.charAt(A_idx) == B.charAt(B_idx))
                distanceBetweenPrefixes[A_idx][B_idx] = computeDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx - 1, distanceBetweenPrefixes);
            else {
                int substituteLast = computeDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx - 1, distanceBetweenPrefixes);
                int addLast = computeDistanceBetweenPrefixes(A, A_idx, B, B_idx - 1, distanceBetweenPrefixes);
                int deleteLast = computeDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx, distanceBetweenPrefixes);
                distanceBetweenPrefixes[A_idx][B_idx] = 1 + Math.min(substituteLast, Math.min(addLast, deleteLast));
            }
        }
 
        return distanceBetweenPrefixes[A_idx][B_idx];
    }
}