행렬 연쇄 곱셈 계산기
행렬 크기 목록을 넣으면 곱하는 순서(괄호)에 따라 스칼라 곱셈 횟수가 얼마나 달라지는지 내고 동적 계획법으로 최적 괄호를 찾습니다. 결과는 같아도 비용은 수십 배 차이가 납니다.
행렬 크기 (곱하는 차례대로)
«10x100 100x5 5x50» 처럼 적습니다. «10 100 5 50» 처럼 차원만 죽 적어도 됩니다. 앞 행렬의 열 수와 뒤 행렬의 행 수는 같아야 합니다.
가장 좋은 순서의 스칼라 곱셈 횟수
7,500번
((AB)C) · 가장 나쁜 순서는 75,000번(10배)
| 행렬 | 크기 | 원소 수 |
|---|---|---|
| A | 10×100 | 1,000 |
| B | 100×5 | 500 |
| C | 5×50 | 250 |
| 괄호 | 곱셈 횟수 | 최적 대비 |
|---|---|---|
| ((AB)C) | 7,500 | 1.00배 |
| (A(BC)) | 75,000 | 10.00배 |
| 구간 | 가르는 자리 | 최소 비용 |
|---|---|---|
| A…B | A 뒤 | 5,000 |
| B…C | B 뒤 | 25,000 |
| A…C | B 뒤 | 7,500 |
계산 방법
- 1행렬 크기를 곱하는 차례대로 «10x100 100x5 5x50»처럼 적습니다.
- 2가장 좋은 순서의 곱셈 횟수와 최적 괄호를 확인합니다.
- 3행렬이 적으면 모든 괄호와 그 비용을 나란히 놓은 표를 봅니다.
- 4DP 표에서 각 구간을 어디서 가르는 것이 최선인지 봅니다.
자주 묻는 질문
결과는 같고 비용만 달라집니다. 행렬 곱에는 결합법칙이 성립해 (AB)C와 A(BC)의 결과 행렬이 완전히 같습니다. 다만 중간에 생기는 행렬의 크기가 달라져 곱셈 횟수는 크게 벌어집니다.
p×q 행렬과 q×r 행렬을 곱으면 스칼라 곱셈이 p·q·r번 듭니다. 결과의 원소가 p·r개이고 원소 하나마다 q번씩 곱하기 때문입니다. 연쇄 곱셈의 비용은 이렇게 센 값을 모두 더한 것입니다.
수십 배에서 수천 배까지 납니다. 10×100, 100×5, 5×50을 곱할 때 (AB)C는 7,500번이지만 A(BC)는 75,000번으로 열 배입니다. 1000×1, 1×1000, 1000×1처럼 벡터가 섞이면 1,000배까지 벌어집니다.
행렬 n개면 카탈랑 수 C(n−1)가지입니다. 4개면 5가지, 6개면 42가지, 11개면 16,796가지이고 21개면 24억 가지가 넘습니다. 그래서 하나씩 세어 보는 방식은 쓸 수 없습니다.
구간을 두 덩어리로 가르는 자리만 따집니다. m[i][j] = min(m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j])로 두면 부분 구간이 O(n²)개이고 각각 O(n)개의 자리를 보므로 O(n³)에 끝납니다. 행렬 11개면 16,796가지 대신 220개의 분할 후보만 보면 됩니다.
행렬 수보다 하나 많게 적습니다. 행렬 3개는 차원 4개(예: 10 100 5 50)로 적으며, i번째 행렬의 크기가 p[i−1]×p[i]입니다. 크기를 «10x100» 꼴로 그대로 적어도 됩니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 스칼라 곱셈 횟수만 셉니다. 덧셈·메모리 이동은 세지 않으므로 실제 실행 시간과 정비례하지 않습니다. 캐시 지역성과 블록 분할이 크게 작용합니다.
- 표준 곱셈법(p·q·r)을 전제합니다. 슈트라센 같은 방법을 쓰면 곱셈 수 자체가 달라져 최적 순서도 바뀔 수 있습니다.
- 행렬은 12개까지 넣을 수 있습니다. 모든 괄호를 나열한 표는 가짓수가 60가지 이하일 때만 나옵니다.
- 실제 값을 곱하지는 않습니다. 값을 넣어 결과 행렬을 구하려면 행렬 계산기를 쓰세요.
- 희소 행렬이나 대각·삼각 행렬처럼 구조가 있는 경우는 다루지 않습니다. 그런 행렬은 곱셈 횟수 자체가 이 식과 다릅니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.