[lecture]5주차.동적계획 알고리즘_연속행렬곱셈

수업을 듣고 정리한 내용입니다.

Chained Matrix Multiplications

동적계획 알고리즘에서 연속행렬곱셈은 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제이다. 이 행렬에서 알고리즘은 결합 법칙을 허용하고, 주어진 행렬의 순서를 지켜서 반드시 이웃하는 행렬끼리 곱하도록 합니다.

//연속 행렬 곱셈
입력 : 연속된 행렬 A1 * A2 ... * An, 단 A1은 d1 * d2, An = d(n-1) * d(n)
출력 : 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수
for i = to n
	C[i,j] = 0
for L = 1 to n - 1
	for i = 1 to n - L
    	j = i + L
        C[i,j] = 무한대
        for k = 0 to j-1
        	temp = C[i,k] + C[k+1,j] + d(i-1)*d(k)*d(j)
            if (temp < C[i,j])
            	C[i,j] = temp

동일한 결과를 얻음에도 불구하고 원소 간의 곱셈 횟수가 차이나기 때문에 적절한 곱셈 순서를 찾는 것이 중요합니다. 부분 문제가 겹쳐 있는 형태는 밑의 그림과 같습니다.

총 부분 문제의 수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2으로 계산되고, 하나의 부분 문제에 대해 k 루프가 최대 (n-1)번 수행하기 때문에 시간복잡도는 O(n^2) * O(n) = O(n^3)입니다.