문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12942
코딩테스트 연습 - 최적의 행렬 곱셈
크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 =
programmers.co.kr
DP를 이용하면 풀 수 있는 문제였습니다.
알고리즘은 아래와 같습니다.
1. cache[i][j]: [i, j] 구간 내 행렬 최소 곱셈 연산 수를 저
2. 구간을 쪼개가며 현재 cache[i][j]와 비교하며 더 작은 연산 값을 저장
3. 2번을 진행한 후 cache[0][matrix_sizes - 1] 값을 반환
개발환경: Programmers IDE
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
| [Programmers] 금과 은 운반하기 (0) | 2022.07.09 |
|---|---|
| [Programmers] 합승 택시 요금 (0) | 2022.07.09 |
| [Programmers] 사라지는 발판 (0) | 2022.06.25 |
| [Programmers] 불량 사용자 (0) | 2022.06.25 |
| [Programmers] 선입 선출 스케줄링 (0) | 2022.06.21 |