[7급 국가직 알고리즘 2025년 21번] 동적 프로그래밍(dynamic programming) 방법으로 최소의 원… 정답과 해설

[7급 국가직 알고리즘 2025년 21번]

동적 프로그래밍(dynamic programming) 방법으로 최소의 원소단위 곱셈 횟수를 갖도록 연쇄 행렬곱셈(matrix-chain multiplication)의 순서를 정하려 한다.

c_{i, j}

를 행렬

M_{i}

부터

M_{j}

까지의 연쇄 행렬곱셈의 최소 비용이라고 할 때,

c_{i, j}

에 대한 관계식으로 옳은 것은? (단,

i < j

이고, 각 행렬의 차원이

p_{0}, p_{1}, ..., p_{n}

일 때, 행렬

M_{i}

의 크기는

p_{i - 1} \times p_{i}

이다)

알고리즘

① $c_{i, j} = {0 min_{i \leq k \leq j - 1} {c_{i, k} + c_{k + 1, j} + p_{i - 1} p_{k} p_{j}} if i = j if i < j$
② $c_{i, j} = {0 min_{i \leq k \leq j - 1} {c_{i, k} + c_{k, j} + p_{i - 1} p_{k - 1} p_{j}} if i = j if i < j$
③ $c_{i, j} = {0 min_{i \leq k \leq j - 1} {c_{i, k - 1} + c_{k, j} + p_{i - 1} p_{k - 1} p_{j}} if i = j if i < j$
④ $c_{i, j} = {0 min_{i \leq k \leq j - 1} {c_{i, k} + c_{k, j} + p_{i - 1} p_{k} p_{j}} if i = j if i < j$

선지를 골라 바로 채점해 보세요.

정답 ①

출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)

신고가 접수됐습니다. 감사합니다.

오류 신고