14.2-1

문제

행렬 괄호 묶기를 직접 해 보는 문제.

풀이

아래처럼 행렬, 차원, 각 차원 별 비용을 정리해놓고 계산하면 된다.

14.2-2

문제

행렬 괄호 묶기 순서(정확히는 인덱스 k만 기록된 배열 s)을 참조해서 실제로 최소 비용으로 행렬 곱셈 연산을 수행하는 재귀 함수 MATRIX-CHAIN-MULTIPLY(A, s, i, j)를 작성해보는 문제.
각 함수에 대한 명세는 아래와 같음.
MATRIX-CHAIN-MULTIPLY(A, s, i, j): <A1, A2, ... An> 행렬 배열 A를 주어진 행렬 s로 행렬 곱셈 수행하는 함수. 초기 호출은 (A, s, 1, n)으로 가정한다.
RECTANGULAR-MATRIX-MULTIPLY(A, B): 두 행렬 A, B에 실제로 행렬 곱셈을 하는 함수.

풀이

배열 s를 활용해서 잘 작성해보면 된다

MATRIX-CHAIN-MULTIPLY(A, s, 1, n) 

MATRIX-CHAIN-MULTIPLY(A, s, i, j)
	if i == j:
    	return A[i]
    k = s[i, j]

	first = MATRIX-CHAIN-MULTIPLY(A, s, i, k)
    second = MATRIX-CHAIN-MULTIPLY(A, s, k+1, j)

	return RECTANGULAR-MATRIX-MULTIPLY(A, B) 

만약 아래와 같은 테이블 s가 있다고 가정했을 때, 5개의 행렬에 대한 MATRIX-CHAIN-MULTIPLY(A, s, 1, n)은 다음과 같다.