jintak0401   4년 전

저처럼 11049번 문제를 풀고 이 문제에 도전하려다가 행렬의 개수와 크기로 난감한 분들께 도움을 드리고자 이 글을 적습니다. 문제가 11049번 문제를 풀었을 때처럼 2차원 배열을 이용해서 풀려고 하면 O(n^3) 의 시간복잡도를 갖게 되어서, 이 문제의 행렬크기로는 시간초과가 될 것 같아서 검색을 해 봤더니 "Hu & Shing Algorithm" 이라는게 있더라구요.

https://en.wikipedia.org/wiki/Matrix_chain_multiplication

여기에서 More Efficient Algorithm 부분을 참고하시면 도움이 되실겁니다. n 개 행렬의 곱셈을 (n + 1) 각형을 삼각형으로 쪼개는 문제로 바꿔서 O(nlogn) 으로 해결하는 알고리즘입니다.

구글에 검색하시면 논문도 나오니 그 논문도 참고하시면 푸실 수 있을거에요

댓글을 작성하려면 로그인해야 합니다.