동적 계획법 알고리즘 문제풀이 기초와 예제(Assembly-line scheduling)

간단하게 요약해 동적계획법이란 복잡한 문제를 푸는 알고리즘의 한 종류로서, 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결 한뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다.

피보나치 수열을 예로 들어보자. 피보나치 수열은 아래와 같이 표현할 수 있을 것이다.

하나의 수열 항목을 구하는 것에 대한 점화식을 알게 되면, 이를 반복하여 큰 문제에 대한 해답을 알아낼 수 있다.

동적 계획법 점화식 구현 방법

우리는 식을 세우는 것에 그치지 않고, 이것을 컴퓨터로 코딩해서 해를 구하는 프로그램을 만들어야 한다. 위 예로 든 피보나치 수열을 동적계획법으로 구현하기 위해서는 세가지 방식을 사용할 수 있을 것이다.

1. 다른 문제에서 가져오는 방식

현재 노드의 값을 구하기 위해서 다른 곳(먼저 계산한 작은 문제) 에서 값을 가져와 해결하는 방식이다. 피보나치 수열을 구하기 위해 먼저 앞의 두 해를 구하고 그 해들을 더해 다음 해를 찾아가게 된다. 아래와 같은 코딩 방식이 될 것이다.

A[0] = 0; 
A[1] = 1;
for(int i=2; i<=N; i++) {
    A[i] = A[i-1] + A[i-2];
}

2. 현재 문제에서 보내주는 방식

다른 문제에서 가져오는 방식과 반대되는 개념이다. 지금 풀어야 하는 작은 문제를 먼저 해결하고, 이 문제에 값을 앞으로 해결할 문제들에게 보내주는 방식이다. 피보나치 수열에서 초기값으로 줄 첫 항목인 0을 다음 두 개의 항목들에 0을 더해준다. 다음 항목인 1을 다음 두 개의 항목들에 더해준다. 그 다음 항목은 앞선 문제에서 더해준 0과 1을 더해 1이 되고, 이 값을 또 다음 두 개의 항목들에 보내줘서 더하는 개념이다. 코드로 구현하면 다음과 같다.

A[0] = 0; 
A[1] = 1;
for(int i=0; i<=N-1; i++){
 A[i+1] += A[i];
 A[i+2] += A[i];
}

3. 메모이제이션(Memoization)

동적계획법이나 재귀호출 등 다음 값을 찾기 위해 기존에 했던 계산을 다시 반복해서 해야 하는 경우가 많다. 이럴 때 한번 계산한 값을 메모리상에 저장해 두고 반복해서 수행해야 할 때에 찾아서 사용하는 방식이다. 동일한 계산이 여러번 반복되는 것을 없애 전체 계산 시간을 줄일 수 있다. 예를 들면 아래 코드처럼 구현할 수 있다.

int getA(int n)
{
    if(A[n] != -1) return A[n];
    if(n == 0) return A[n] = 0;
    if(n == 1) return A[n] = 1;
    return A[n] = getA(n-1) + getA(n-2);
}

동적 계획법 문제에 대한 풀이 : Assembly-line scheduling

위 그림과 같은 생산 라인에서 최소 경로를 구하는 문제이다. D[i][j]를 물건이 i번 생산라인의 j번째 공정에 있을 때, 오는데 걸리는 최소 시간으로 생각하자.

초기값은 아래와 같이 줄 수 있을 것이다.

D[1][1] = E[1] + S[1][1]

D[2][1] = E[2] + S[2][1]

여기서 물건이 i번 생산라인의 j번째 공정에 오게 되는 상황에서의 경로는 물건이 직전에 i번 생산라인의 j-1번째 공정으로부터 오거나, 3-i번 생산라인의 j-1번째 공정에서 오는 경우일 것이다.

물건이 i번 생산라인의 j-1번째 공정에서 오는 경우에 대한 것은 "D[i][j-1]" 일 것이다. 반면에 물건이 3-i번 생산라인의 j-1번째 공정에서 오는 경우에는 라인을 이동하는 시간을 더해 "D[3-i][j-1] + t[3-i][j-1]" 로 표현할 수 있다.

따라서 이 경우의 최적 해는 "D[1][N] + X[1]" 와 "D[2][N] + X[2]" 둘 중 작은 값일 것이다.

점화식으로 풀어보면 "D[i][j] = min(D[i][j-1], D[3-i][j-1] + t[3-i][j-1]) + S[i][j]" 으로 표현할 수 있을 것이다.

이를 자바 코드로 코딩하면 다음은 로직으로 풀 수 있다. 다른 문제에서 가져오는 방식을 사용했다.

D = new int[3][N+1];
for (int i=1;i<3;i++) D[i][1] = E[i] + S[i][1];
for (int j=2;j<=N;j++){
    for (int i=1;i<3;i++){
        D[i][j] = Math.min(D[i][j-1],
                    D[3-i][j-1] + T[3-i][j-1]) + S[i][j];
    }
}
System.out.println("#" + ts + " " + Math.min(D[1][N] + X[1], D[2][N] + X[2]));