DP문제 설계 Rod-Cutting, Matrix-Chain Multiplications

https://guhonga.tistory.com/116

Dynamic Programming (Fibonacci, Rod-Cutting Problem)

Rod-Cutting

 

이전에 Rod-Cutting 문제에 대해 다뤄봤었다.

여기서 구한 Rod-Cutting 에 대한 bottom up 알고리즘은 최적의 값만 계산해줄 뿐이지, 밧줄의 어떤 부분을 잘라야 할지는 알려주지 않았다.

 

그래서 이번에는 maximum revenue 값, r[j] 뿐만 아니라
처음 자를 때의 최적의 크기 s[j] 도 구할 것이다.

s를 구하는 알고리즘은 다음과 같다.

 

이전에 구했던 테이블과 비교해보면, 각 길이에 따른 가격만 나와있던 것에서 추가된 것을 확인할 수 있다.

여기에서 밧줄의 길이 5가 의미하는 것은 2칸째(가격 5)에 잘라서 3칸이 남았고(가격 8) 최적의 수익이 13인 것을 볼 수 있다.

 

 

---

 

 

Matrix-Chain Multiplication

<A1, A2, ...An> 같이 n개의 행렬이 차례대로 주어질 때, 이 행렬들의 곱을 계산하는 문제이다.
당연히 그냥 계산하는 것은 아니고 계산적인 비용을 최소화 시키면서 해야한다.

행렬을 배웠으면 알겠지만 A X B라고 할 때, A행렬의 열과 B 행렬의 행의 수가 같을 때 두 행렬을 곱할 수 있다.

이 개념을 바탕으로 행렬 곱의 비용을 알아보자.

A와 B를 곱해서 행렬 C를 만들었다. 이 행렬의 행과 열은 p와 r이다.

그래서 이와 같은 계산으로 행렬 C를 만드는데 필요한 연산의 비용은
A의 행들의 element와 B의 열들의 element를 곱해서 C 행렬의 element '하나'를 만들었다.
이 과정으로 C 행렬 전부를 계산하려면 q 번 반복해야 한다. (직접 계산해보면 앎)

그래서 행렬 C를 계산하는데 필요한 computational cost는 pqr이다.

 

 

그런데 행렬의 곱셈은 행렬들을 어떻게 각각 곱하는지에 따라 달라질 수 있다. (괄호로 묶어서 먼저 따로 계산)

예를들어 <A1,A2,A3> 행렬곱이 있다고 하자.
A1는 10*100, A2는 100*5, A3는 5*50 일 때

(A1A2)A3 순서는 (10*100*5) + (10*5*50) = 7500

A1(A2A3) 순서는 (10*100*50) + (100*5*50) = 75000 으로 괄호에 따라 계산 비용이 달라진다.

 

잠깐 주의할 점이 있다. 우리가 하고자 하는 것은 실제 행렬 곱을 구하는 것이 아니라 가장 적은 계산 비용만을 구하는 것이다.

 

 

 

우선 naive한 접근을 해보자. (brute force 방식)

1. 가능한 모든 괄호를 열거한다 (얼마나 될지도 모름..)
2. 각 괄호의 곱셈 개수를 계산한다 
3. 곱셈이 가장 적게 필요한 괄호를 선택한다

여기서 P(n)은 행렬 n개들의 가능한 괄호 개수이다.
재귀의 하한을 통해 계산했는데 너무 크다.. DP로 더 효율적으로 계산해보자.

 

 

지금까지 해왔던 DP 방식대로

1. 하위 문제 파악
2. 하위 문제에 대한 솔루션 저장
3. main 문제에 대한 최적의 솔루션 구축

이 단계를 따라서 문제를 설계해보자.

 

먼저 하위 문제를 식별하자.

행렬들의 곱 Ai * Ai+1 * ... * Aj 로부터 행렬들의 곱셈 결과를 설정한다.

 

다음으로 각 하위 문제들의 최적화된 솔루션들을 결합하여 main problem을 구한다.

 

이 과정을 구하기 위한 최소 비용 행렬 m[ i , j ]은 다음과 같은 알고리즘을 따른다.

subproblem을 저장할 배열 (n X n) m과 (n-1 X n) s을 선언하고 자기 자신의 곱은 0으로 채웠다.

임의로 곱할 행렬들의 길이(괄호로 묶인 길이) l 만큼 반복을 선언한다.

모든 가능한 행렬 chain의 길이와 시작점을 고려하기 위해서 l이 2부터 n까지 반복하고, i가 1부터 (n-l+1)까지 반복한다.
이때 j는 i+l-1로 설정되고 m[i][j]는 무한대로 초기화한다. j가 가리키는 i+l-1은 현재 고려하고 있는 행렬 chain의 끝 점을 나타낸다.
예를 들어, i가 1이고 l이 2라면 우리는 행렬 1과 2를 곱하는 비용을 계산하게 된다.
이때 j는 1+2-1 = 2가 되어 행렬 2를 가리킨다.

이렇게 행렬 chain의 최소 곱셈 비용을 계산하고, 이것을 m[i][j]에 저장한다. 
이 과정에서 최적의 k 값도 함께 저장하여 나중에 최적의 해를 구할 수 있게 한다.

 

 

예를 들어 행렬 <A1,...,A6> 의 최소 비용을 구해보자.  

여기에서 (1,1) 이나 (2,2)는 자기 자신부터 자기 자신까지의 곱셈 비용이니 0이다.

위 알고리즘에 따르면 (1,3) 즉, A1부터 A3까지의 곱셈은 A1(A2A3) 또는 (A1A2)A3의 경우가 있다.

우선 m[1,3]은
m[1,1] + m[2,3] + p0p1p3 또는 m[1,2] + m[3,3] + p0p2p3으로 나타낼 수 있다.

m[1,1] + m[2,3] + p0p1p3 = 0 + 2625 + 30*35*5 = 7875
m[1,2] + m[3,3] + p0p2p3 = 앞에 계산해놓은 15750 + 0 + 30*15*5 = 18000 으로
m[1,3] 테이블에는 7875가 저장된다.

아래는 matrix chain에서 k가 가리키는 값을 나타낸 표이다.

 

 

행렬 테이블이 알고리즘의 어떤 부분에 대응하는지 볼 수 있다.

 

 

이와 같은 알고리즘의 시간 복잡도는 반복문이 3개 있으므로 O(n^3)이고,
공간 복잡도는 m과 s 테이블을 갖고 있으니 O(n^2)을 가질 것이다.