행렬코딩

행렬은 알고리즘 문제를 풀 때도 그렇고, 3D 코딩을 할때도 필요하고 여러모로 쓸 경우가 많은것 같아 여기 정리합니다.

먼저 나이브한 행렬곱셈을 구현해보면 다음과 같습니다. (관련 문제: 백준 2740번 행렬곱셈)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll A[101][101], B[101][101], C[101][101];
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%lld", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%lld", &B[y][x]);
 
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            for (int i = 0; i < m; i++) 
                C[y][x] += A[y][i] * B[i][x];
            
            printf("%lld ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}

특별할건 없고, 2차원 배열로 잡고 y, x (또는 행, 열 이라고도 표현 가능) 순으로 인덱스 할당해서 계산한다는 것..

근데 한가지 불편한점이 발견되는것은 곱셈결과를 리턴하도록 함수로 뺄 경우에 행렬을 리턴값으로 두기 까다롭다는 것이다 (2차원 배열이니까.. 한가지 work around는 걍 out-value 파라미터를 사용하는것.. 하지만 그렇더라도 리턴값처럼 복사기반이 아니기 때문에 값의 정합성(오버라이팅 된다거나..)에 대해 항상 고민해야한다.) 

따라서 자연스럽게 2차원배열 그 자체로 쓰는것보다 struct나 class로 빼는걸 생각하게 되는데.. 대입연산자나 생성자, 소멸자, 멤버함수등 생각할게 많아지고 코드의 단순함이 많이 훼손(?)된다.

vector의 vector를 사용하면 위의 리턴문제를 비교적 간단하게 해결할 수 있다. 아래 코드를 보자.

#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix mul(matrix A, matrix B)
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%d", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%d", &B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = mul(A, B);
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}

연산자 오버로딩을 사용하면 mul 함수대신 * 기호를 사용할수도 있다. 다음을 보자.

#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix operator * (matrix A, matrix B) 
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d", &n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++) 
        scanf("%d", &A[y][x]);
 
    int k; scanf("%d %d", &m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++) 
        scanf("%d", &B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = A * B;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}