18236번 - 행렬 곱셈 순서 2
저처럼 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) 으로 해결하는 알고리즘입니다.
구글에 검색하시면 논문도 나오니 그 논문도 참고하시면 푸실 수 있을거에요
댓글을 작성하려면 로그인해야 합니다.
jintak0401 4년 전 12
저처럼 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) 으로 해결하는 알고리즘입니다.
구글에 검색하시면 논문도 나오니 그 논문도 참고하시면 푸실 수 있을거에요