사용자 도구

사이트 도구


ps:problems:programmers:12942

최적의 행렬 곱셈

ps
링크https://programmers.co.kr/learn/courses/30/lessons/12942
출처프로그래머스
문제 번호12942
문제명최적의 행렬 곱셈
레벨Level 4
분류

동적 계획법

시간복잡도Optimal: O(nlogn), 실제구현: O(n^3)
인풋사이즈n<=200
사용한 언어Python
해결날짜2021/01/21

풀이

  • 동적 계획법의 유명한 문제인 연쇄 행렬 곱셈문제이다.
  • O(nlogn) 알고리즘이 최적으로 알려져 있지만, 여기에서는 교과서에서 알려주는 O(n^3) 알고리즘으로 풀었다.
  • 추후에 O(nlogn) 알고리즘을 구현해보고 업데이트 예정.
  • BOJ의 행렬 곱셈 순서도 동일한 문제이지만, n<500 이라서 코드를 조금 더 최적화시켜야 통과 가능하다.

코드

"""Solution code for "Programmers 12942. 최적의 행렬 곱셈".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12942
- Solution link: http://www.teferi.net/ps/problems/programmers/12942
"""


def solution(matrix_sizes):
    n = len(matrix_sizes)
    dp = [[0] * n for _ in range(n)]
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] +
                matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]
                for k in range(i, j))

    return dp[0][-1]

토론

댓글을 입력하세요:
M T᠎ I V᠎ T
 
ps/problems/programmers/12942.txt · 마지막으로 수정됨: 2021/03/04 14:06 저자 teferi