시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
행렬 연쇄 곱셈 II 문제에서 우리는 행렬의 차원을 제공하고 모든 행렬의 곱셈과 관련된 연산 수가 최소화되도록 곱셈 순서를 찾습니다.
각각 크기가 axb, bxc, c xd 인 3 개의 행렬 A, B, C가 있다고 가정합니다. 그런 다음 먼저 A와 B 행렬을 곱하고 그 결과에 C를 곱하면이 총 연산에는 (axbxc + axcxd)가 걸립니다. 행렬의 곱셈 순서를 변경하면. 먼저 B와 C 행렬을 곱한 다음 그 결과에 A를 곱합니다.이 총 연산에는 (bxcxd + axbxd)가 필요합니다. 이것은 행렬에서 곱셈 순서가 변경되면 수행되는 연산 수에 영향을 미친다는 것을 보여줍니다. 따라서 주어진 모든 행렬을 곱하기 위해 수행 할 수있는 최소 연산 수를 찾아야합니다.
차례
예
Input: number of matrices = 3
Dimensions of matrices = {1, 2, 3, 4}
Output: 18
설명 : 먼저 행렬에 1 x 2 및 2 x 3 차원을 곱하면 6 개의 작업 비용이 발생합니다. 그런 다음 행렬 C에 A와 B를 곱한 결과 행렬을 곱합니다.이 연산은 다시 1 x 3 x 4를 사용하여 총 18 개의 연산을 만듭니다.
Input: number of matrices = 2
Dimensions of matrices = {10, 10, 20}
Output: 2000
설명 : 행렬이 두 개뿐이기 때문에 총 2000 개의 연산이 필요한 행렬을 곱하는 단일 방법 만 있습니다.
행렬 연쇄 곱셈에 대한 접근 방식
행렬 곱셈 문제는 많은 표준 중 하나입니다. 동적 프로그래밍 문제. 행렬을 곱하는 모든 방법을 시도하는 재귀 적 접근 방식을 간단히 생각할 수 있습니다. 우리는 모든 준비에 관련된 총 비용을 찾고 모든 준비에서 최소한의 금액을 취합니다. 재귀 솔루션은 확실히 우리에게 정확한 결과를 제공하지만 충분히 효율적이지 않습니다. 재귀 솔루션이 있고 하위 문제가 겹칠 때마다. 작은 하위 문제의 결과를 저장 한 다음 이러한 결과를 결합하여 초기 문제를 해결할 가능성이 있습니다. 이 문제는 사용할 때마다 계산되는 하위 문제가 겹칩니다. 따라서 결과를 dp 테이블에 저장하거나 정렬.
먼저 단일 문제를 해결합니다. 매트릭스, 0 작업 비용이 발생합니다. 단일 행렬을 구한 후, 우리는 2 개의 행렬을 풀고 3을 구하는 식입니다. 일반적인 경우, 인덱스 i에서 j까지의 행렬에 대한 문제를 풀어야한다고 생각하십시오. 상향식으로 문제를 해결하고 있기 때문입니다. i에서 j까지의 행렬을 풀 때, i에서 j-1, j-2까지의 행렬 문제에 대한 결과를 계산했습니다. 따라서이를 해결하기 위해 i에서 j까지의 행렬에 대한 문제를 먼저 해결한다고 생각합니다. k, 행렬 k + 1에서 j까지의 문제. 그런 다음이 모든 값의 최소값을 취하십시오.
매트릭스 체인 곱셈을위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int matrixMultiplicationProblem(vector<int> matrixSize) {
int numberOfMatrices = matrixSize.size()-1;
// dp[i][j] = minimum number of operations required to multiply matrices i to j
int dp[numberOfMatrices][numberOfMatrices];
// initialising dp array with INT_MAX ( maximum number of operations )
for(int i=0;i<numberOfMatrices;i++){
for(int j=0;j<numberOfMatrices;j++){
dp[i][j] = INT_MAX;
if(i == j) // for a single matrix from i to i, cost = 0
dp[i][j] = 0;
}
}
// start solving problem for 2 matrices, then 3, and so on.
for(int len=2;len<=numberOfMatrices;len++){
for(int i=0;i<numberOfMatrices-len+1;i++){
int j = i+len-1;
for(int k=i;k<j;k++)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
}
}
return dp[0][numberOfMatrices-1];
}
int main() {
int t;cin>>t;
while(t--) {
int n; cin>>n;
vector<int> matrixSize(n);
for(int i=0;i<n;i++)cin>>matrixSize[i];
cout<<matrixMultiplicationProblem(matrixSize)<<endl;
}
}
2 5 // number of inputs = dimensions of n-1 matrices 5 6 89 49 10 // dimensions of ith matrix = matrixSize[i]*matrixSize[i+1] 7 1 5 2 3 4 1000 64
26925 68028
매트릭스 체인 곱셈을위한 자바 코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int matrixMultiplicationProblem(int matrixSize[]) {
int numberOfMatrices = matrixSize.length-1;
// dp[i][j] = minimum number of operations required to multiply matrices i to j
int dp[][] = new int[numberOfMatrices][numberOfMatrices];
// initialising dp array with Integer.MAX_VALUE ( maximum number of operations )
for(int i=0;i<numberOfMatrices;i++){
for(int j=0;j<numberOfMatrices;j++){
dp[i][j] = Integer.MAX_VALUE;
if(i == j) // for a single matrix from i to i, cost = 0
dp[i][j] = 0;
}
}
// start solving problem for 2 matrices, then 3, and so on.
for(int len=2;len<=numberOfMatrices;len++){
for(int i=0;i<numberOfMatrices-len+1;i++){
int j = i+len-1;
for(int k=i;k<j;k++)
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]));
}
}
return dp[0][numberOfMatrices-1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0) {
int n = sc.nextInt();
int matrixSize[] = new int[n];
for(int i=0;i<n;i++)
matrixSize[i] = sc.nextInt();
int ans = matrixMultiplicationProblem(matrixSize);
System.out.println(ans);
}
}
}
2 5 // number of inputs = dimensions of n-1 matrices 5 6 89 49 10 // dimensions of ith matrix = matrixSize[i]*matrixSize[i+1] 7 1 5 2 3 4 1000 64
26925 68028
복잡성 분석
시간 복잡도 : O (N ^ 3)
여기서는 O (N ^ 2)에서 실행되는 행렬의 경계 역할을하는 두 개의 포인터 i와 j를 고려하고 있습니다. 외부 루프 자체 내부의 중첩 루프는 선형 시간 O (N)을 사용합니다. 따라서 알고리즘은 총 O (N ^ 3)에서 실행됩니다.
공간 복잡성 : O (N ^ 2)
차원이 N x N 인 2D dp 배열을 사용했기 때문에 총 O (N ^ 2)가됩니다.
