[C/C++] 백준 2740번 : 행렬 곱셈

백준 2740번 행렬 곱셈에 대한 C, C++ 코드를 풀이해보자.

백준 2740번 : https://www.acmicpc.net/problem/2740

 

1. 문제

 

 

선형대수학의 행렬곱 문제이다.

N*M 크기의 A배열과 M*K 크기의 B배열의 곱을 구해야한다.

 

2. 행렬곱

결과 행렬의 크기는 A의 행과 B의 열의 곱이다. 따라서 A의 열의 개수와 B의 행의 개수가 같아야 구할 수 있다.

행렬곱의 각 원소는 간단히 말해서, A의 행과 B의 열을 곱한 후 합산해서 구한 값이다.

따라서 결과 행렬 C의 i행 j열은 A의 i행과 B의 j열의 원소들을 각각 곱한 후에 모두 더한 값이 된다.

 

3. 풀이

다시 문제로 돌아가서 행렬곱을 이용해 예제 문제를 풀어보면,

 

 

4. 코드

풀이한 문제를 코드로 구현해보자. 아래는 C언어 코드이다.

#include <stdio.h>
#include <string.h>

int main() {
	int n, m, m2, k;
	scanf("%d %d", &n, &m);
	
	int a[n][m];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d", &a[i][j]);
		}
	}
	
	scanf("%d %d", &m2, &k);
	
	int b[m2][k];
	
	for(int i=0; i<m2; i++){
		for(int j=0; j<k; j++){
			scanf("%d", &b[i][j]);
		}
	}
	
	int result[n][k];
	memset(result, 0, sizeof(result));
	
	for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            for(int l=0; l<m; l++){
                result[i][j] += a[i][l] * b[l][j];

            }
        }
	}
	
	for (int i = 0; i < n; i++) {  
        for (int j = 0; j < k; j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }
}

 

memset을 이용하여 결과 행렬을 초기화 해주었다.

for(int i=0; i<n; i++){
    for(int j=0; j<k; j++){
        for(int l=0; l<m; l++){
            result[i][j] += a[i][l] * b[l][j];
        }
    }
}

 

위 로직을 통하여 행렬곱을 계산하였다. A의 i 행과 B의 j 열을 곱하였음을 알 수 있다.

 

아래는 C++ 코드이다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m, m2, k;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    cin >> m2 >> k;

    vector<vector<int>> b(m2, vector<int>(k));
    for (int i = 0; i < m2; i++) {
        for (int j = 0; j < k; j++) {
            cin >> b[i][j];
        }
    }

    vector<vector<int>> result(n, vector<int>(k, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            for (int l = 0; l < m; l++) {
                result[i][j] += a[i][l] * b[l][j];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

행렬곱을 계산하는 로직은 C언어와 같다.

 

 

 

 

행렬곱셈만 알면 그리 어렵지 않은 문제였던 것 같다. 감사합니다 (* 'ᵕ' )ﾉ