매트릭스 연쇄 곱셈 문제에서 괄호 인쇄

난이도 하드
자주 묻는 질문 아마존 아 발라 라 데이터 브릭 지시 JP 모건 Paytm Twilio
배열 동적 프로그래밍 매트릭스조회수 81

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

모든 행렬의 곱셈과 관련된 연산의 수가 최소화되도록 행렬의 곱셈 순서를 찾아야합니다. 그런 다음이 순서를 인쇄해야합니다. 즉 행렬 연쇄 곱셈 문제에서 괄호를 인쇄해야합니다.

각각 크기가 axb, bxc, c xd 인 3 개의 행렬 A, B, C가 있다고 가정합니다. 행렬을 곱할 수있는 두 가지 경우가 있습니다. 먼저 A와 B를 곱한 다음 C를 곱하거나 먼저 B와 C를 곱한 다음 A를 곱합니다. 첫 번째 선택은 (axbxc + axcxd)의 비용이 발생하는 반면 두 번째 옵션은 총 (bxcxd + axbxd) 작업을 수행합니다. 관련된 연산의 수가 행렬의 곱셈 순서에 따라 다르다는 것을 알 수 있습니다. 따라서 최소 연산 수를 가져 오는 행렬의 곱셈 순서를 찾아야합니다. 

number of matrices = 3

Dimensions of matrices = {1, 2, 3, 4}
((AB)C)

 

설명 : 먼저 행렬에 1 x 2 및 2 x 3 차원을 곱하면 6 개의 작업 비용이 발생합니다. 그런 다음 행렬 C에 A와 B를 곱한 결과 행렬을 곱합니다.이 연산은 다시 1 x 3 x 4를 사용하여 총 18 개의 연산을 만듭니다.

number of matrices = 2

Dimensions of matrices = {10, 10, 20}
(AB)

설명 : 행렬이 두 개뿐이기 때문에 총 2000 개의 연산이 필요한 행렬을 곱하는 단일 방법 만 있습니다.

행렬 연쇄 곱셈 문제에서 괄호를 인쇄하는 방법

우리는 이미 해결했습니다 행렬 연쇄 곱셈 문제 모든 행렬의 곱셈과 관련된 최소 연산 수를 찾아야했습니다. 매트릭스 체인 곱셈을 사용하여 동적 프로그래밍 이 문제의 전제 조건입니다. 행렬 곱셈 문제를 조금만 수정하면 괄호를 인쇄 할 수 있습니다. 대괄호 [i] [j]가 최적의 인덱스를 저장하는 대괄호 행렬을 만듭니다. 인덱스 i, j 앞뒤에 경계 [i, j]의 모든 행렬이 곱해지면 인덱스가 최적입니다. 그 결과 결과가 곱 해져 필요한 최소 작업 수를 제공합니다. 이것은 우리가 먼저 최적 인덱스에 대한 행렬 i와 최적 인덱스 + 1에서 j까지의 행렬에 대한 결과를 찾은 다음 그 결과를 결합한다는 것을 의미합니다.

대괄호 행렬을 사용하여 행렬 주위에 대괄호를 인쇄합니다. 우리는 단일 행렬을 얻을 때까지 문제를 하위 문제로 계속 나누고 인쇄합니다.

매트릭스 연쇄 곱셈 문제에서 괄호 인쇄

Matrix Chain Multiplication 문제에서 괄호를 인쇄하기위한 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// Recursively print the arrangement for minimum cost of multiplication
void printBracketsMatrixChain(int i, int j, vector<vector<int>> &brackets, char &cur_name){
    
    // you have a single matrix ( you cannot further reduce the problem, so print the matrix )
    if(i == j){
        cout<<cur_name;
        cur_name++;
    } else {
        cout<<"(";
        
        // Reduce the problem into left sub-problem ( left of optimal arrangement )
        printBracketsMatrixChain(i, brackets[i][j], brackets, cur_name);
        
        // Reduce the problem into right sub-problem ( right of optimal arrangement )
        printBracketsMatrixChain(brackets[i][j]+1, j, brackets, cur_name);
        cout<<")";
    }
}

void 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;
        }
    }

    vector<vector<int>> brackets(numberOfMatrices, vector<int>(numberOfMatrices, 0));
    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++) {
                int val = dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]);
                if(val < dp[i][j]) {
                    dp[i][j] = val;
                    brackets[i][j] = k;
                }
            }
        }
    }

    // naming the first matrix as A
    char cur_name = 'A';
    
    // calling function to print brackets
    printBracketsMatrixChain(0, numberOfMatrices-1, brackets, cur_name);
    cout<<endl;
}

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];
        matrixMultiplicationProblem(matrixSize);
    }
}
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
(((AB)C)D)
(((((AB)C)D)E)F)

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static char cur_name;
    
    // Recursively print the arrangement for minimum cost of multiplication
    static void printBracketsMatrixChain(int i, int j, int brackets[][]){
        
        // you have a single matrix ( you cannot further reduce the problem, so print the matrix )
        if(i == j){
            System.out.print(cur_name);
            cur_name++;
        } else {
            System.out.print("(");
            
            // Reduce the problem into left sub-problem ( left of optimal arrangement )
            printBracketsMatrixChain(i, brackets[i][j], brackets);
            
            // Reduce the problem into right sub-problem ( right of optimal arrangement )
            printBracketsMatrixChain(brackets[i][j]+1, j, brackets);
            System.out.print(")");
        }
    }

    static void 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;
            }
        }
    
        int brackets[][] = new int[numberOfMatrices][numberOfMatrices];
        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++) {
                    int val = dp[i][k]+dp[k+1][j]+(matrixSize[i]*matrixSize[k+1]*matrixSize[j+1]);
                    if(val < dp[i][j]) {
                        dp[i][j] = val;
                        brackets[i][j] = k;
                    }
                }
            }
        }
    
        // naming the first matrix as A
        cur_name = 'A';
        
        // calling function to print brackets
        printBracketsMatrixChain(0, numberOfMatrices-1, brackets);
        System.out.println();
    }

    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();
            matrixMultiplicationProblem(matrixSize);
        }
    }

}

 

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
(((AB)C)D) 
(((((AB)C)D)E)F)

 

복잡성 분석

시간 복잡도 : O (N ^ 3)

여기서는 O (N ^ 2)에서 실행되는 행렬의 경계 역할을하는 두 개의 포인터 i와 j를 고려하고 있습니다. 외부 루프 자체 내부의 중첩 루프는 선형 시간 O (N)을 사용합니다. 그래서 알고리즘이 O (N ^ 3) 전체적으로.

공간 복잡성 : O (N ^ 2)

다항식 공간 복잡성은 O (N ^ 2) 2D DP 어레이가 있기 때문입니다.

균열 시스템 설계 인터뷰
Translate »