머가필요해

이번에 살펴볼 Dynamin Programming 알고리즘은

Matrix-Chain Multiplication (연쇄 행렬 곱셈)이다.

[Background]

우선 알아야할 내용은 바로 "행렬 곱" 규칙이다.

'행렬 곱'을 하기 위해서는 앞 행렬의 column 길이와 뒤 행렬의 row 길이가 같아야 한다.

그러면, 앞 행렬의 row 와 뒤 행렬의 column 길이만큼의 결과가 나온다.

두번째로 알아야할 내용은 행렬 곱에서 '결합 법칙'이 성립한다는 것이다.

그런데, 여기에서 우리가 주의깊게 살펴봐야할 사실이 하나 등장한다.

행렬 곱에서 결합을 어떻게 하는지에 따라 계산 횟수가 달라진다는 것이다.

위의 예시와 같이 3개의 행렬이 주어졌을 때,

계산 횟수를 살펴보면 10배의 차이가 발생한다는 것을 알 수 있다.

[Problem]

그러면 우리가 여기에서 해결하고자 하는 문제가 무엇일까?

곱셈을 해야하는 여러 행렬이 순서대로 주어졌을 때,

어떻게 결합을 해야 전체 계산 횟수를 최소화 할 수 있을지를 찾아내는 것이다.

[Brute force approach]

일단 무식하게 살펴보자.

총 4개의 행렬이 주어졌을 때, 총 5가지의 묶음 방법이 존재한다.

이를 분류해보면

앞에서부터 1개 묶음을 하면 총 2종의 결합 방법이 존재하고

2개 묶음을 하면 1종,

3개 묶음을 하면 2종의 결합 방법이 있기에 총 5종의 결합 방법이 있게 된다.

이 과정을 공식으로 살펴보면 다음과 같다.

공식을 유도하고 분석하는 것은 생략하도록 하겠다.

그런데, 이를 Asymptotic 하게 생각해보면, 다음과 같다.

마찬가지로 계산식 유도 및 분석은 생략하고.... 결론적으로 엄청난 경우의 수가 나오기에...

이렇게 문제를 푸는 것은 말이 안됨! ^^

[Solution]

똑똑하게 문제를 풀어보자.

지금까지 살펴본 내용을 공식화한 것으로 생각하면 된다.

위 공식을 가지고 직접 손으로 계산을 해보자.

행렬에 따라서 row와 column은 다음과 같이 살펴볼 수 있다.

왜 이렇게 표현이 되는지 이해가 안되면 안된다.

앞에서 충분히 살펴본 내용을 곰곰히 생각해보면 된다.

예시를 하나 들어보자.

행렬이 6개가 주어졌다고 했을 때, p값이 다음과  같이 제시 되었다고 해보자.

이 문제를 풀기 위해 우리는 m, s 행렬을 작성해야 한다.

왜 이렇게 하는지는 문제를 풀어보면서 알아보자.

위 공식을 살펴보면 알겠지만,

i=j 조건에서는 모두 0 값을 갖게 되고 i보다 j는 항상 커야 되기 때문에 표의 아랫부분은 계산하지 않아도 된다.

m[1][2] 값부터 계산해보면 위와 같이 정리해볼 수 있다.

k값은 ( i ≤ k < j ) 조건이므로 ( 1 ≤ k < 2 )와 같고, 그렇기 때문에 k값은 1밖에 갖을 수 없다.

s 행렬의 s[1][2] 값은 k값이 1이므로 1값을 작성하면 된다.

이런식으로 m[2][3], m[3][4], m[4][5], m[5][6] 부분을 채울 수 있다.

이번에는 m[1][3]을 계산해보자.

앞에서와 달리 k값은 ( 1 ≤ k < 3 )이므로, k값은 1, 2 의 2가지 경우가 있을 수 있다.

그러므로, 최종 결과가 2개 나오고, 그 중에서 min 값을 선택하면 된다.

k값이 1인 경우를 선택했으므로 s[1][3] 위치에는 1을 작성하면 된다.

하나씩 하나씩 이렇게 채워나가면 된다.

전부 채우면 다음과 같다.

끝~

[Pseudo Code]

이 과정을 가지고 pseudo code로 만들어보자.

이렇게 만들어진 결과물을 출력하기 위한 code는 다음과 같다.

[Time & Space]

time complexity 와 memory space를 계산해보면 다음과 같다.

먼저 Time Complexity를 살펴보자.

무려 n의 3승 이다.

메모리 공간을 계산해보면 다음과 같다.

알고리즘을 위해 추가로 사용하는 메모리는 m, s 배열이 필요하다.

Asymptotic 하게 해보면.... 결국은 n의 제곱만큼의 공간을 필요로 한다.

왠지 이름만 들어도 어려울 것 같은 느낌이 팍팍 드는, Dynamic Programming !!!

연구비를 타내기 위해 그냥 있어보이려고 멋지게 작명하다보니 이런 이름을 가졌다고 한다.

사람 사는게 다 그렇지 뭐~ ^^

"Dynamic Programming"은 뭔가 계산하는 알고리즘이라기 보다는

작은 문제를 풀어서 그 중간 결과를 기록해 놓음으로써 다시 재계산하지 않도록 하는 방법이다.

여러 유형의 문제를 Dynamic Programming으로 푸는 것을 살펴볼텐데

그 첫번째로 살펴볼 것이 바로 "Assembly-line scheduling" 이다.

[Definition]

'Assembly-line'이라는 것에 대한 정의 부터 살펴보자.

컨베이어벨트를 따라 단계별로 부품 조립하는 것을 생각하면 된다.

- station : 조립 단계. 제품 조립은 n개의 station을 거치면 완성이 된다.

- a : 각 station 단계에서 소요되는 시간

- line : 하나의 컨베이어 벨트로 생각하면 된다.

- e : line에 조립을 시작하도록 하기 위해 소요되는 시간

- x : 조립 완료된 제품을 전달하기 위해 소요되는 시간

- t : line을 옮기기 위해 소요되는 시간

[Problem]

여러 line으로 구성된 assembly-line이 있을 때,

어떤 경로가 가장 짧은 소요 시간으로 조립할 수 있는지 최적의(가장 빠른) 경로를 찾는 방법은?

[Solution-1]

가장 확실하고 무식한(?) 방법으 모든 경우의 수를 구해서 찾는 방법이다.

하지만, 말 그대로 무식한 방법이기에 ... 경우의 수가 너무 크다.

[Solution-2]

스마트한 방법을 찾아보자.

▷ Idea

어느 시점(S)에서 자기 순서까지 올 수 있는 방법은 2가지 경우 밖에 없다.

자기가 있는 동일한 line의 직전 단계에서 오는 방법과, 다른 line의 직전 단계에서 오는 2가지의 경우이다.

그러면, 그 2가지의 경우 중에 가장 빠른 것을 선택하면 되게 되는 것이다.

▷ How to

그러면 예시를 살펴보자.

각 단계에서 소요되는 시간을 더해가면서 정리하면 된다.

보다 더 짧은 시간을 선택하면 되기 때문에 □로 표기된 값들이 선택된 결과들이다.

이렇게 선택하는 과정에서 소요되는 Running Time은 어떻게 될까?

각 Station에서 2개씩 값을 보면 되기 때문에 2n의 Running Time이 필요하고,

entry + exit 과정이 있기 때문에 이를 정리하면 다음과 같다.

Brute-force 방법으로 할 때에는 어느 시점(S)에서 자기한테 까지 오는 모든 경우의 수를 살펴보지만

지금 방식에서는 바로 직전의 2가지 경우만 살펴보기 때문에 n에 비례하는 복잡도를 갖게 되었다.

그러면, 중간에 각 S단계에 따른 값들을 어떻게 저장하면 될까?

위와 같은 표 내용만 기록/기억 하고 있으면 되는 것이다.

그런데, 이 것만 가지고는 어떤 경로로 구성된 것인지 알기가 어렵다.

이 내용을 기록할 표가 하나 더 필요한 것이다.

그런데, 2개의 테이블이 모두 필요할까?

경로만 확인 가능해도 되는 경우에는 L table만 있으면 된다.

S table은 현재 값과 직전 값만 알면 되고, 최적해(S* = 38) 값만 저장하면 된다.

S table에서 S3를 계산할 때 S2 값만 알면 된다. 즉, S1의 내용은 필요 없다.

메모리를 굳이 table 전체 크기만큼 잡아 놓지 않아도 된다는 것이다.

L table 값만 알면 최적 경로를 찾을 수 있기 때문이다.

반대로 S 값을 갖고 있는 table만 있어도 L 값 table 없이 경로를 찾아낼 수는 있다.

하지만 L 값 table을 사용하는 것이 훨씬 더 편하기에 L Table을 이용하는 것이다.

▷ Pseudo Code

코드로 구현해보면 다음과 같다.

뭔가 복잡해보이는데, 살펴보기 편하게 구분해보면 다음과 같다.

결과를 출력하는 부분은 아래와 같이 구현해볼 수 있다.

실행 결과는 다음과 같이 나올 것이다.

▷ Space consumption

일단 기본적으로는 S table과 L table 모두 필요로 한다는 전제 하에 다음과 같은 메모리 사용량을 필요로 한다.

▷ Running time

하나의 요소 別 소요 시간이 Θ(1) 소요시간이 걸린다고 했을 때, 전체 소요 시간은 Θ(n)이라고 할 수 있다.

뭔가 심오한 Dynamic Programming의 세계이다~