프로그래머스: 최적의 행렬 곱셈⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
난이도 ⭐⭐⭐
유형 : DP
🧐 문제
문제 설명
크기가 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 |
입출력 예 설명
입출력 예#1
문제의 예시와 같습니다.
🧐 입력 조건
처음봤을때 아래 조건이 모호하게 느껴진다.
“계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.”
여기서 해석 방법이 두가지로 나뉜다.
- [[5,6],[7,3],[2,4]]처럼 애초에 연산이 불가능한 행렬이 들어온다.
- [[5,3],[3,10],[10,6]]와 같이 순서대로 들어온다.
[[3,10],[5,3],[10,6]] 혹은 [[5,3],[10,6],[3,10]]처럼 순서가 섞여 계산할 수 없는 행렬이 들어오지 않는다.
헷갈리지만, 일반적인 행렬의 특징에 따라 2번 해석으로 생각해야 한다.
🔍 힌트
matrix_sizes = [[5,3],[3,10],[10,6],[6,5],[5,4]]
위 입력을 부르기 편하게 ABCDE로 정의한다.
최소 곱셈 연산 수 또한 최연수라고 부르겠다.
이제 ABCDE 행렬을 결합하는 방법에는 총 4가지가 있으며, 각 결합 방법의 연산 수들을 아래와 같이 구할 수 있다.
| 연산 | 곱셈 연산 수 |
|---|---|
| [A][BCDE] | A 최연수(0) + BCDE 최연수 + A와 BCDE 결합 연산 수(5*3*4) |
| [AB][CDE] | AB 최연수 + CDE 최연수 + AB와 CDE 결합 연산 수(5*10*4) |
| [ABC][DE] | ABC 최연수 + DE 최연수 + ABC와 DE 결합 연산 수(5*6*4) |
| [ABCD][E] | ABCD 최연수 + E 최연수(0) + ABCD와 E 결합 연산 수(5*5*4) |
이제 이 4가지 연산 수들중 가장 작은 녀석이 ABCDE의 최연수이다.
이번엔 BCDE의 최연수를 구해보자.
| 연산 | 곱셈 연산 수 |
|---|---|
| [B][CDE] | B 최연수(0) + CDE 최연수 + B와 CDE 결합 연산 수(3*10*4) |
| [BC][DE] | BC 최연수 + DE 최연수 + BC와 DE 결합 연산 수(3*6*4) |
| [BCD][E] | BCD 최연수 + E 최연수(0) + BCD와 E 결합 연산 수(3*5*4) |
BCDE의 최연수 = 3가지 연산 수 중 가장 작은 녀석
이번엔 DE의 최연수를 구해보자.
| 연산 | 곱셈 연산 수 |
|---|---|
| [D][E] | D 최연수(0) + E 최연수(0) + D와 E 결합 연산 수(6*5*4) |
이런식으로 큰 문제를 작은 문제로 나눌수 있다는 점에서 DP라는 것을 알아낼 수 있다.
한번 연산된 최연수는 DP 배열속에 저장해두었다가, 사용하면 된다.
✏️ 나의 풀이
#include <bits/stdc++.h>
using namespace std;
int dp[201][201];
int multiply(int s, int e, vector<vector<int>>& matrix_sizes) {
if(s==e) return 0;
if(dp[s][e]!=0) return dp[s][e];
int min_val = INT_MAX;
for(int k=s; k<e; k++) {
int mul = matrix_sizes[s][0] * matrix_sizes[k][1] * matrix_sizes[e][1];
int temp = multiply(s, k, matrix_sizes) + multiply(k+1, e, matrix_sizes) + mul;
min_val = min(min_val, temp);
}
return dp[s][e] = min_val;
}
int solution(vector<vector<int>> matrix_sizes) {
return multiply(0, matrix_sizes.size()-1, matrix_sizes);
}
✔️ 다른 사람의 풀이
#include <vector>
using namespace std;
int solution(vector<vector<int>> matrix_sizes) {
int size = matrix_sizes.size();
vector<vector<int>> dp(size, vector<int>(size, 999999999));
for (int i = 0; i < size; i++)
dp[i][i] = 0;
int a, b;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i; j++) {
if (j == j + i)
continue;
a = j;
b = j + i;
for (int k = a; k < b; k++)
dp[a][b] = min(dp[a][b],
dp[a][k] +
dp[k + 1][b] +
matrix_sizes[a][0] *
matrix_sizes[k][1] *
matrix_sizes[b][1]
);
}
}
return dp[0][size - 1];
}
🧐 분석
- 재귀가 아닌, 2중 포문을 사용하여 구현하고 있다.
- i와 j를 통해 a(left), b(right)를 설정하고 있다.
🪶 후기
문제를 처음 보았을때 “계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.”라는 조건이 제일 헷갈렸다.
그래서 질문하기 탭에 들어가서 확인한 뒤에야 생각을 확실히 할 수 있었다.
이 문제를 처음 접했을때 DP를 써야하는건가 헷갈렸었다.
처음엔 “원형 큐와 비슷한 원리를 사용해서 ABC, BCA, CAB 순으로 연산을 각각 해보자. 그리고 가장 작은 녀석을 선택하면 되지 않을까?” 라고 생각했다.
그렇게 어느정도 짜다보니까 반례가 생각이 났다.
그렇게 한참을 이리저리 행렬을 가지고 놀다가..
DP문제라는 것을 알게 됐고, 점화식도 구했다.
막상 코드로 옮겨보니까 되게 쉬운 문제였는데, 생각을 하는데만 너무 오래 걸렸다.
앞으로는 시간을 정해두고, 스탑워치를 켜놓은 채 문제를 풀어야 시간도 절약하고 문제에 확실히 집중할 수 있을것 같다.
| 난이도 | 시간 |
|---|---|
| ⭐ | 5분 |
| ⭐⭐ | 20분 |
| ⭐⭐⭐ | 40분 |
| ⭐⭐⭐⭐ | 60분 |
| ⭐⭐⭐⭐⭐ | 80분 |
그래서 위와 같이 나의 수준과 문제 난이도에 따라 시간을 정해봤다.
다음부턴 풀이 경과 시간에 대한 정보도 같이 올려야겠다.
댓글남기기