곱셈 가능한 4개의 연쇄행렬 A_1A_2A_3A_4가 주어졌을 때, 동… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
곱셈 가능한 4개의 연쇄행렬 A1A2A3A4가 주어졌을 때, 동적 프로그래밍(dynamic programming) 방법으로 최소 곱셈 횟수를 갖도록 연쇄행렬 곱셈(matrix-chain multiplication)의 순서를 찾으려 한다. 1≤i≤j≤4를 만족하는 i,j에 대하여, <보기 1>과 같이 s[i,j]에 Ai⋯Aj가 최소 곱셈 횟수를 갖도록 Ai⋯Ak와 Ak+1⋯Aj로 분할하는 위치 k를 저장할 때, <보기 2>의 알고리즘으로 출력되는 연쇄행렬 곱셈의 순서로 가장 옳은 것은? (예를 들어, s[1,2]=1)
<보기 1>
1
2
3
4
1
1
1
1
2
2
2
3
3
4
테이블 s
<보기 2>
PRINT(s, i, j)
if i == j
print “A”i
else print “(”
PRINT(s, i, s[i, j])
PRINT(s, s[i, j]+1, j)
print “)”
1
(((A1A2)A3)A4)
2
((A1(A2A3))A4)
3
(A1((A2A3)A4))
4
(A1(A2(A3A4)))
해설
출력되는 순서는 (A1(A2(A3A4)))이다.
PRINT(s, 1, 4)는 s[1,4]=1이므로 A1과 A2⋯A4로 나눈다.
PRINT(s, 2, 4)는 s[2,4]=2이므로 A2와 A3A4로 나누고, s[3,4]=3으로 A3과 A4가 분리된다. 결국 매번 왼쪽 첫 행렬을 떼어내는 괄호가 된다.