문제
크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다.
예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.
행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.
각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.
제한
- 행렬의 개수는 3이상 200이하의 자연수입니다.
- 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
- 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.
입출력 예시
| matrix_sizes | result |
|---|---|
| [[5,3],[3,10],[10,6]] | 270 |
풀이
먼저 행렬의 곱셈이 어떤 방식으로 연산이 이루어지는지 이해가 필요하다. 문제 설명에서 대략적으로 설명해주고 있지만, 행렬의 기본적인 수학 연산에 대해 파악하고 있지 않다면 무슨 소리인지 잘 이해가 가지 않을 수 있다. (본인이 그러했다)
행렬의 곱셈은 문제 설명에서 나온 것과 같이 A by B 크기인 행렬과 B by C 크기인 행렬 처럼 하나의 크기가 일치해야한다. 여기서는 B크기가 일치하기 때문에 곱셈이 가능하다. 곱셈의 연산 횟수는 A x B x C번 발생한다. 그리고 중요한 것은 곱셈 연산의 결과로 도출되는 행렬의 크기는 A by C가 된다는 것이 중요하다. 때문에 2개 이상의 행렬이 있을때 어떤 순서로 곱셈을 하냐에 따라 곱셈 연산의 수가 달라질 수 있는 것이다.
이런 규칙을 먼저 파악하고 문제를 풀어보자. 사실 해당 문제 자체가 연쇄행렬 최소곱셈(Matrix chain multiplication) 알고리즘으로 존재하는데, 해당 알고리즘을 사용하기까지 하나씩 차근차근 살펴볼 것이다.
1) 마지막 결합 형태
행렬이 5개만 되더라도 상당수의 결항형태가 존재한다. 주어진 행렬 개수의 최대값이 200개이기 때문에 200개까지 일일이 각 순서를 고려하여 최대값을 하나씩 구하는 연산은 당연히 시간초과가 발생할 것이다.
일단 다음과 같이 5개의 행렬이 있다고 생각해보자.
그림에서 제시하고 있는 순서 외에도 다양한 순서가 존재한다. 그리고 순서에 따라 곱셈 연산의 횟수가 매번 달라지는 것을 알 수 있다. 그런데 앞에서 설명한 바와 같이 행렬의 곱셈이 이루어지기 위해서는 두 행렬에서 일치하는 숫자가 무조건 존재해야 한다. 위 예시에서 A 행렬은 4x3 크기의 행렬이도 B 행렬은 3x2 크기의 행렬인 걸 볼 수 있다. 이때 3이 서로 일치하기 때문에 두 행렬은 곱셈이 가능하다. 그리고 곱셈의 결과로 나오는 행렬의 크기는 4x2가 될 것이다. 때문에 그 뒤에 있는 C 행렬과의 곱셈도 가능하고, 그 결과 역시 뒤에 있는 D, E ... 행렬들과 곱셈 역시 가능하다.
따라서 우리는 행렬을 어떤 순서로 곱하든간에 상관없이 최종적으로 가질 수 있는 마지막 결합형태를 찾을 수 있다. 항상 두 행렬을 곱해주기 위해서는 하나의 숫자를 일치시켜주어야 하기 때문이다. 이때 결합형태의 가짓수는 항상 행렬의 개수 - 1을 만족한다. 행렬을 곱하기 위해서는 최소 두 개가 필요하기 때문이다. 이를 그림으로 나타내면 다음과 같다.
따라서 최소값은 위 4가지 결합형태에 해당하는 방법들 중에 가장 적은 곱셈 연산 횟수가 될 것이다. 이때 각 결합형태를 구성하는 두 묶음이 필요한데, 하나의 묶음에서 어떤 행렬이 최종적으로 도출되기 까지 다시 여러 순서로 곱셈 연산이 발생할 수 있다. 이 과정에서 우리는 중복되는 연산이 발생하리라는 것을 미루어 알 수 있다. 때문에 해당 문제를 DP 알고리즘을 적용하여 접근할 것이다.
2) DP 점화식
위 과정에서 우리는 결합형태가 고정적으로 존재한다는 것을 파악했다. 그리고 결합형태의 한 묶음은 다시 여러 행렬의 곱으로 나타날 수 있다. 우리는 이들 행렬의 곱셈 횟수를 DP배열에 저장해 줄 것이다. 행렬은 3개이상 연속해서 나타날 수 있기 때문에, DP 배열을 다음과 같이 정의하자.
DP[i][j] = i번째 행렬부터 j번째 행렬까지 최소 연산 횟수
다만 곱셈 횟수는 순서에 따라 달라질 수 있고, 또 우리가 찾고자 하는 값은 최소값이기 때문에 기존값과 비교해 더 작을때 갱신되어야 할 것이다. 이를 다음의 식으로 나타낼 수 있다.
DP[i][j] = Math.min(DP[i][j], X)
따라서 우리는 X값에 들어갈 식을 구해주어야 한다. 예를 들어 위의 그림에서 Type1번을 보자. 두 묶음 중 하나는 행렬 B x C x D x E로 이루어져 있다. 때문에 이들 행렬의 최소 곱셈 연산 횟수를 DP[B][E]로 나타낼 수 있다. 그런데 이들 역시 여러개의 행렬로 구성되어 있기 때문에 순서에 따라 횟수는 매번 달라진다. 순서가 달라진다는 것은 행렬의 기준이 되는 지점이 매번 달라진다는 것이다.
가령 C를 기준으로 삼았다면 B x C 곱셈이 수행되고 이 결과에 나머지 D, E 행렬과 곱셈이 가능하다. 즉 DP[B][C] + DP[D][E]으로 분류해서 생각할 수 있다. 이때 각각의 DP 배열은 B x C 행렬과 D x E 행렬 곱셈의 최소 연산 횟수만을 담고 있다. 즉 두 행렬의 곱셈 결과로 나온 두 행렬에 곱셈은 아직 고려하지 않고 있다. 때문에 이 두 행렬의 곱셈 횟수 역시 추가로 고려해주어야 한다. 이는 주어진 matrix_sizes 배열을 통해 할 수 있다.
DP[B][C] + DP[D][E] + ( matrix_sizes[B][0] x matrix_sizes[D][0] x matrix_sizes[E][1] )
이는 앞서 살펴보았듯이 행렬의 곱셈은 항상 하나의 숫자가 일치할 때 가능하기 때문에, 행렬 B x C의 크기는 B[0] x B[1] x C[1] = B[0] by C[1]이 되고 행렬 D x E의 크기는 D[0] x D[1] x E[1] = D[0] by E[1]이 된다. 이때 문제 조건에 의해 항상 B[1] === D[0]이 성립하기 때문에 B[0] by C[1]과 D[0] by E[1] 행렬은 서로 곱셈이 가능하다. 이때의 크기는 당연히 B[0] x D[0] x E[1]이 될 것이다. (이때 B[0] x B[1] x E[1] 역시 동일하기 때문에 가능하다)
이는 위에서 기준을 C로 잡았을 때의 경우이다. 이때 몇 개의 행렬이 있냐에 따라 하나씩 기준을 달리하며 위의 점화식을 적용시킨다면 DP[i][j]의 최소값을 구할 수 있을 것이다.
따라서 우리는 다음의 점화식을 도출할 수 있다. 이때 기준값이 되는 값을 k라고 하자.
DP[i][j] = Math.min(
DP[i][j],
DP[i][k] + DP[k+1][j] + ( matrix_sizes[i][0] * matrix_sizes[k+1][0] * matrix_sizes[j][1] )
);3) DP 알고리즘 구현
점화식을 찾았으므로 이를 바탕으로 DP를 구현해보자. 점화식과 마찬가지로 중요한 건 초기 DP 배열 초기화이다. 우리가 찾아야 할 것은 최소값이기 때문에 만약 계산된 값이 더 작을 경우 갱신하도록, 배열의 초기값은 Infinity로 설정하자.
앞서 보았듯이 2차원 배열을 사용하여 접근할 것이다. 이때 배열의 개수는 당연히 matrix_sizes로 주어지는 행렬의 개수 n이 될 것이다. dp[n]에는 역시 n개의 Infinity 값을 가지고 있는 배열을 추가해주자. 이는 행렬이 i, j, k 있다고 했을때 dp[i][i], dp[i][j], dp[i][k]로 접근할 수 있음을 말한다. dp[i][i]와 같이 곱셈이 불가한 경우는 0으로 초기화를 진행해주자.
const n = matrix_sizes.length;
const dp = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
for(let i = 0; i < n; i ++) {
dp[i][i] = 0;
}우리는 위에서 n개의 행렬이 있을때 n-1개의 결합 형태가 나타남을 보았다. 따라서 가장 외부에 있는 반복문은 n-1번 만큼 순회하며 값을 찾아갈 것이다.
반복문 내부에서 우리가 필요한 값은 dp 배열에서 시작하는 행렬의 위치 start, 마지막 지점의 행렬 위치 end 그리고 기준이 되는 행렬의 위치 fixed가 필요하다. 이는 앞서 살펴본 DP[i][k] + DP[k+1][j]에서 각각의 i, k, j와 일치한다.
문제 조건에 의해 계산할 수 없는 행렬은 입력으로 주어지지 않기 때문에 순서는 앞에서부터 차례대로 보장되어 있다. 따라서 start 값은 0부터 시작하고 이에 대한 end 값은 현재 start + i 값이 될 것이다. 만약 이 값이 행렬의 개수 n 보다 크거나 같아지는 순간에는 반복을 종료해야 한다.
기준이 되는 fixed는 start ~ end 범위에서 한 지점씩 선택하게 될 것이다. 따라서 해당 범위에서 값을 하나씩 늘려가도록 지정해줄 수 있고, 이 내부에서 우리가 구한 점화식을 적용하도록 하자. 위 과정을 코드로 구현하면 아래와 같다.
// n-1개의 마지막 결합 형태가 있기 때문에 그만큼 반복
for(let i = 1; i < n; i++) {
for(let start = 0; start < n; start++) {
const end = start + i; // 마지막 지점의 위치
if (end >= n) break; // 행렬 범위를 벗어나는 경우
// 기준의 위치는 start ~ end 범위 내에 있다
for(let fixed = start; fixed < end; fixed++) {
// 위에서 구한 점화식 적용
// matrix_sizes[fixed+1][0]의 경우 matrix_sizes[fixed][1]로 해도 상관없다
dp[start][end] = Math.min(
dp[start][end],
dp[start][fixed] + dp[fixed+1][end] + (
matrix_sizes[start][0] * matrix_sizes[fixed+1][0] * matrix_sizes[end][1]
)
);
}
}
}4) 정답 리턴
반복문을 돌며 점화식을 통해 dp 배열의 값을 모두 구하고 나면, 최종 리턴해야 할 정답은 dp[0][n-1]에 담겨있다. 우리가 처음 DP[i][j]의 배열을 만들때 의미를 생각해보자. DP[i][j]는 i번째 행렬부터 j번째 행렬까지에 발생한 곱셈 연산의 최소값을 담고있다. 우리가 구해야 하는 것은 주어진 행렬 전체에 대한 곱셈 연산의 최소값이기 때문에 dp[0][n-1]을 리턴해야 한다.
5) 전체코드
연쇄행렬 최소곱셈 알고리즘을 접해보지 못했거나, 행렬에 대한 기초 상식이 없었다면 상당히 풀기 어려운 문제가 될 것 같다. 그러나 핵심이 되는 점화식과 DP 배열의 정의를 차근차근 되짚어본다면 사실 쉽게 이해할 수 있는 문제이다. 물론 점화식을 도출하는것이 DP 알고리즘의 핵심이니 만큼 이 과정에 다다르는 것 자체가 어려운 일이라는 것은 십분 공감한다. 적당한 난이도의 Lv.4 문제가 아닌가 싶다. 주석을 제외한 전체코드는 다음과 같다.
function solution(matrix_sizes) {
const n = matrix_sizes.length;
const dp = new Array(n).fill().map(_ => new Array(n).fill(Infinity));
for(let i = 0; i < n; i++) {
dp[i][i] = 0;
}
for(let i = 1; i < n; i++) {
for(let start = 0; start < n; start++) {
const end = start + i;
if (end >= n) break;
for(let fixed = start; fixed < end; fixed++) {
dp[start][end] = Math.min(
dp[start][end],
dp[start][fixed] + dp[fixed+1][end] + (
matrix_sizes[start][0] * matrix_sizes[fixed+1][0] * matrix_sizes[end][1]
)
);
}
}
}
return dp[0][n-1];
}출처
