[알고리즘] 동적 계획 알고리즘(DP) 유형 별 문제 모음

 

 

분할 정복 알고리즘은 반으로 나누는 것이 핵심이었다. 정확히는 분할할 수 없을 때까지 분할하여 간단한 문제부터 접근하였다. 굉장히 자주 사용하며, 좋은 알고리즘이다. 하지만, 분할하며 생기는 부분 문제들이 중복되어도 다시 사용하지 않는다.

 

 

 

이미 구한 문제를 또 푸는 것은 지루하고 시간이 드는 일이다. 유형마다 다르겠지만, 분할정복도 마찬가지일 것이다. 따라서 중복된 문제를 굳이 다시 풀지 않는 테크닉이 필요하다. 그리고 그 방법이 바로 "DP 알고리즘", Dynamic Programming 인 것이다.

 

 

 

DP 알고리즘은 미리 최소 부분 문제들의 해를 구한다. 이는 논리적으로 생각했을 때 매우 당연하다고 여겨지는 것들이다. 또한 이 해를 이용하여 최소 부분 문제보다 더 큰 부분 문제를 풀어야 한다.

 

 

 

즉, 부분 문제와 부분 문제 사이에 어떤 관계가 정의되어 있다는 것을 유추할 수 있다. 이 관계는 문제나 입력에 따라 다르고, 대부분은 뚜렷이 보이지 않아 "함축적 순서"라고 부른다. 그래서 그런지 더럽게 어렵기도 하다.

 

 

 

분할 정복 vs. DP 알고리즘

 

 

수도 코드를 통해 어떤 차이점이 있는 지 먼저 확인해 보자.

널리 알려져 있는 막대 자르기 문제를 적용시켰다.

 

 

분할 정복 아이디어

cutRod_DC(p[], i)
// 길이 i의 막대를 판매할 때 얻을 수 있는 최대 판매 금액, R(i)를 계산한다.
// 입력 : p[1 ... n] - 막대들의 판매 가격
// i - 막대의 길이
// 출력(반환값) : 최대 판매 금액

if (i == 0) return 0
else {
    maxSell = 0
    for(j=1; j<=i; j++) {
        maxSell = MAX(maxSell, p[j] + cutRod_DC(p, i-j))
        return maxSell
    }
}


// 최초 호출
maxSellValue = cutRod_DC(p, n)

 

 

 

제일 중요한 식 Max(maxSell, p[j] + cutRod_DC(p, i-j)를 R(n)이라고 해보자. 이 R(n)은 길이가 n인 막대를 판매했을 때, 얻을 수 있는 최대의 금액을 의미한다.

 

 

 

p[j]라는 막대의 길이에 맞는 가격으로 판매한 후, 남은 길이에 대해 재귀적으로 cutRod_DC(p, 남은 길이)를 호출하는데, 자세히 살펴보면 j 자체가 1~i까지 모든 케이스를 확인하기 때문이다.

 

 

 

이때의 시간 복잡도는 지수시간으로 매우 길다. 그 풀이는 아래와 같다.

 

식1 : T(n) = 1 + (T(n-1) + T(n-2) + ... + T(1) + T(0)), n>=1

식2 : T(n-1) = 1 + (T(n-2) + T(n-3) + ... + T(1) + T(0))

식1 - 식2 = T(n) - T(n-1) = T(n-1)

T(n) = 2 * T(n-1) = 2 * (2*T(n-2)) = 2^2(2*T(n-2))

= 2^n * T(0) = 2^n

 

 

 

 

 

DP 아이디어

cutRod_DP(p[], n)
// 길이 n의 막대를 판매할 때, 얻을 수 있는 최대 판매 금액을 계산
// 입력 : p[1...n] - 막대들의 판매 금액, n : 막대의 길이
// 출력(반환값) : 최대 판매 금액

배열 maxSell[0...n] 선언
maxSell[0] = 0
for(j = 1; j<=n; j++) {
    maxVal = 0
    for(k = 1; k<=j; k++) {
        maxVal = MAX(maxVal, p[k] + maxSell[j - k])
    maxSell[j] = maxVal
    }
}

return maxSell[n]

 

 

여기서 차이점이 될 만한 부분은 MAX(...) 부분이다. 해당 부분에서 재귀적으로 호출하던 분할 정복과 달리 그냥 maxSell[j-k]를 호출하고 있다. 대신 초기에 maxSell에 대한 배열 선언을 우선적으로 해야 한다.

 

 

 

이렇게 DP 알고리즘을 사용하여 막대 길이 구하기 문제를 풀면 시간복잡도는 O(n^2)이 나온다.

 

 

 

 

 

 

 

모든 쌍 최단 경로 문제

 

 

최단 경로를 찾는 알고리즘은 다익스트라나 플로이드 워샵 등여러가지가 있다. 각각의 장단점이 있겠지만은, 간단함으로 따지면 플로이드 워샵이 가장 좋다. 최단 경로에 대해 궁금하다면 아래 링크에서 확인하자.

 

 

[알고리즘] 최단 경로 알고리즘 - Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘

 

 

앞서 말했듯이 DP 문제는 부분 문제들의 "함축적 순서"의 관계로 이루어져 있다고 하였다. 그렇다면 이 문제에서 보이지 않는 부분 문제들간의 관계는 무엇일까?

 

 

 

이를 파악하기 앞서 부분 문제는 어떻게 정의해야 하는 지부터 알아야 한다. 핵심은 경로를 찾는 문제라는 것이다. 이를 위해 특정 위치에서 다른 위치까지 이동하는데, 직접가는 것과 어딘가를 경유해서 가는 것 중 짧은 것을 택해야 한다. 즉, 부분 문제는 "경유해서 가는 것과 직접 가는 것 중 짧은 것을 택"하는 것으로 정의할 수 있다.

 

 

A에서 C로 가는데, B를 경유해서 가는게 더 빠를 지 그렇지 않을 지 알아야 한다.

 

 

 

 

정의된 부분 문제에 따라서 DP 배열을 만든다면 아래와 같이 만들 수 있다.

 

DP = 점 {1, ... , k } 를 경유 가능한 점으로 고려하여, 점 i에서 j까지의 모든 경로 중 가장 짧은 경로의 거리

 

 

여기서 k를 경유하는 것이 가장 짧은 경로를 가는 것이 아니라면 쓰지 않는다.

 

 

 

 

🔲 가장 작은 부분 문제

 

$D_{ij}^{1}$의 모든 점 i와 j에 대해 가장 작은 부분 문제를 계산한다.

 

 

 

 

 

 

 

🔲 $D_{ij}^{2}$ 의 경우

 

 

 

점 i에서 점 2를 경유하여 j로 가는 경우와 i에서 j로 바로 가는 경우 중 최소값을 선택한다. 경유하는 경우라면 $D_{i2}^{1}+D_{2j}^{1}$가 된다.

 

$D_{i2}^{1}$ 를 계산하는 과정에서 이전에 풀었던 부분 문제 해를 사용한다.

 

 

🔲 $D_{ij}^{k}$ 의 경우

 

i에서 k를 경유하여 j로 가는 경우와 바로 i에서 j로 가는 경우 중 최소 값을 찾는다.

 

 

 

 

 

 

 

 

 

 

모든 쌍 최단 경로 문제의 수도 코드

 

 

앞서 알아본 개념에 따르면 쉽게 코드를 작성할 수 있다.

 

 

for k = 1 to n
    for i = 1 to n(i != k)
        for j = 1 to n(j != k, j!=i)
            D[i, j] = min{ D[i, k] + D[k, j], D[i, j] }

 

 

 

 

 

 

현재 노드 간의 가중치를 나타낸 행렬이다.(음수 가중치 포함)

 

왼쪽 배열을 보고 오른쪽 최단 거리를 갱신하는 과정을 직접 해보는 것을 추천한다.

 

 

 

 

 

 

 

연속 행렬 곱셈

 

 

연속 행렬 곱셈은 연속된 행렬 간의 곱셈의 최소 횟수를 구하는 문제이다. 문제를 풀려면 행렬의 곱셈 법칙에 대해서 선행 학습이 되어야 한다. 일단 난 안 했었다.

 

 

 

행렬 곱셈은 결합 법칙이 적용된다. A x B x C = (A x B) x C = A x (B x C) 라는게 적용된다는 말이다.

또한 행렬 곱셈을 위해서는 앞의 요소는 열, 뒤의 요소는 행이 일치해야 한다. 예를 들어 (10 x 5 행렬) * (5 x 15 행렬)이어야 곱셈이 성립한다는 것이다. 그리도 해당 곱셈의 결과로는 앞의 요소에서 행과 뒤에 요소에서 열을 가져오면 되기 때문에 10 x 15가 그 결과이다.

 

 

 

 

행렬 곱셈을 압시다.

 

 

 

 

 

앞서 말했듯이 행렬 곱셈은 결합 법칙이 적용되기 때문에 어떤 연산을 먼저 하느냐에 따라 그 횟수가 달라진다. 즉, A x B를 먼저하냐, B x C를 먼저하냐가 곱셈 횟수의 중요한 요인이다.

 

 

 

그렇다면 부분문제는 어떻게 정의할 수 있을까? 이는 (A), (AxB), (AxBxC)와 같이 연속된 행렬곱의 조합으로 두면되며 이 크기만 잘 조절하면 된다.

 

 

 

 

 

 

 

 

 

연속 행렬 곱셈의 수도 코드

 

입력 : 연속된 행렬 A1 x A2 x A3 ... An, 단 A1은 d0 x d1, A2는 d1 x d2, ... An은 dn-1 x dn이다.

출력 : 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수

for i = 1 to n
    C[i, i] = 0
for L = 1 to n-1
    for i = 1 to n-L
        j = i + L
        C[i, j] = 무한대

        for k=i to j-1
            $temp=[ \left[ i,k\right] +[ \left[ k+1,j\right] +d_{i-1}d_{k}d_{j}$
            if (temp < C[i, j])
                C[i, j] = temp


return C[1, n]

 

 

 

 

🔲 입력을 보고 A1 ~ An까지가 행렬 곱이라는 것부터 파악한다.

 

🔲 C는 모든 부분 문제들로 이루어진 배열이다.(DP 배열)

 

🔲 L은 부분 문제의 사이즈를 조절한다. 특이한 점은 L이 1일때, 부분 문제의 크기는 2, L이 2일 때 부분 문제의 크기는 3... n-1일때는 부분 문제의 크기가 n이다. (L이 1이면 부분 문제는 A1 x A2와 같이 된다.)

 

🔲 i는 부분 문제의 시작 인덱스, j는 부분 문제의 끝 인덱스를 뜻한다. k는 그 사이의 것들로 이를 통해 각 경우의 부분 문제 케이4스들을 처리한다.

 

🔲 $temp=[ \left[ i,k\right] +[ \left[ k+1,j\right] +d_{i-1}d_{k}d_{j}$에서 앞의 C배열 두개는 곱하고자 하는 행렬 두개를 의미한다. 마지막 $d_{i-1}d_{k}d_{j}$는 실제로 곱했을 때의 곱셈 횟수이다.

 

 

 

 

 

 

 

 

 

편집 거리 문제(Edit Distance)

 

 

편집 거리 문제는 삽입, 삭제, 대체 연산을 사용하여 문자열 S를 문자열 T로 변환할 때 필요한 편집 연산 횟수를 구하는 문제이다. 앞선 두 문제보다는 쉬우니 바로 부분 문제 정의부터 해보자.

 

 

 

E[i, j] = S의 처음 i개 문자를 T의 처음 j개의 문자로 바꾸는 데 필요한 편집 거리

 

예를들어, 'strong' -> 'stone'에 대해 'stro' -> 'sto'로 바꾸기 위한 편집 거리는 E[4, 3]이다.

 

 

 

 

🔲 E[4, 3]을 구하려면?('stro' -> 'sto')

 

1️⃣ E[4,2] + 1

E[4, 2]를 알고 있는 상태에서 E[4, 3]을 구하려면 'o'를 하나 더해야 한다. 즉, E[4, 2] + 1 (T가 증가하면 삽입 연산)

2️⃣ E[3, 3] + 1

E[3, 3]을 알고 있는 상태에서 E[4, 3]을 구하려면 E[4, 3]에서 'o'를 빼야 한다.(S가 증가하면 삭제 연산)

3️⃣  E[3, 2] + 0(혹은 1인데, 예시의 경우 0)

E[3, 2]를 알고 있는 상태에서 E[4, 3]을 구해야 한다. 이때 S와 T가 둘다 증가하여도 대체가 없으므로 0을 더한다.(둘다 'o')

 

 

 

 

 

 

해당 예시를 일반화 하면 아래와 같은 관계식을 도출할 수 있다.

 

 

 

 

 

 

 

 

편집 거리 문제(Edit Distance)의 수도 코드

 

 

 

EditDistance
입력 : 스트링 S, T, 단, S와 T의 길이는 각각 m과 n이다.
출력 : S를 T로 변환하는 편집 거리, E[m, n]

// 행과 열 초기화
for i = 0 to m E[i, o] = i;
for j = 0 to n E[0, j] = j;

for i = 1 to m
    for j = 1 to n
        E[i, j] = min { E[i, j-1] + 1, E[i-1, j] + 1, E[i-1, j-1] + a }

return E[m, n]

 

 

 

 

 

 

 

 

 

 

배낭 코드 & 거스름돈 문제

🔲 배낭 문제 수도 코드

Knapsack
입력 : 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 wi와 가치 vi
출력 : k[n, C]

// 배낭 용량이 0일 때
for i=0 to n K[i, 0] = 0

// 물건 0이란 어떤 물건도 고려하지 않
for w=0 to C K[0, w] = 0

for i=1 to n
    for w=1 to C // 배낭의 임시 용량
        if (wi > w) // 물건의 무게가 용량보다 초과
            K[i, w] = K[i-1, w] // 현재 배낭 용량이 w인 경우에서의 최대 가치
        else // 물건 i를 배낭에 담지 않을 경우와 담을 경우를 고려함
            K[i, w] = max{ K[i-1, w], K[i-1, w-wi] + vi}

return K[n, C]

 

🔲 거스름돈 문제

 

입력 : 거스름돈 n원, k개의 동전의 액면, d1 > d2 > ... > dk = 1
출력 : C[n]

for i = 1 to n C[i] = 무한대
C[0] = 0
for j = 1 to n
    for i = 1 to k
        if (di <= j) and (C[j-di] + 1 <= C[j])
            C[j] = C[j-di] + 1
return C[n]