곱셈 가능한 4개의 연쇄행렬 A_1A_2A_3A_4가 주어졌을 때, 동… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
곱셈 가능한 4개의 연쇄행렬 A1A2A3A4A_1A_2A_3A_4가 주어졌을 때, 동적 프로그래밍(dynamic programming) 방법으로 최소 곱셈 횟수를 갖도록 연쇄행렬 곱셈(matrix-chain multiplication)의 순서를 찾으려 한다. 1≤i≤j≤41\le i\le j\le 4를 만족하는 i, ji,\ j에 대하여, <보기 1>과 같이 s[i, j]s[i,\ j]에 Ai⋯AjA_i\cdots A_j가 최소 곱셈 횟수를 갖도록 Ai⋯AkA_i\cdots A_k와 Ak+1⋯AjA_{k+1}\cdots A_j로 분할하는 위치 kk를 저장할 때, <보기 2>의 알고리즘으로 출력되는 연쇄행렬 곱셈의 순서로 가장 옳은 것은? (예를 들어, s[1, 2]=1s[1,\ 2]=1)
<보기 1>
1234
1111
222
33
4
테이블 ss
<보기 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)(((A_1A_2)A_3)A_4)
2
((A1(A2A3))A4)((A_1(A_2A_3))A_4)
3
(A1((A2A3)A4))(A_1((A_2A_3)A_4))
4
(A1(A2(A3A4)))(A_1(A_2(A_3A_4)))
해설

출력되는 순서는 (A1(A2(A3A4)))(A_1(A_2(A_3A_4)))이다.

PRINT(s, 1, 4)는 s[1,4]=1s[1,4]=1이므로 A1A_1과 A2⋯A4A_2\cdots A_4로 나눈다.

PRINT(s, 2, 4)는 s[2,4]=2s[2,4]=2이므로 A2A_2와 A3A4A_3A_4로 나누고, s[3,4]=3s[3,4]=3으로 A3A_3과 A4A_4가 분리된다. 결국 매번 왼쪽 첫 행렬을 떼어내는 괄호가 된다.

  • (((A1A2)A3)A4)(((A_1A_2)A_3)A_4): s[1,4]=3s[1,4]=3, s[1,3]=2s[1,3]=2일 때의 결과다.
  • ((A1(A2A3))A4)((A_1(A_2A_3))A_4): s[1,4]=3s[1,4]=3, s[1,3]=1s[1,3]=1일 때의 결과다.
  • (A1((A2A3)A4))(A_1((A_2A_3)A_4)): s[2,4]=3s[2,4]=3일 때의 결과다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기