행렬의 다양한 연산들

간단하게 행렬을 표현하는 방법에서 코딩 테스트에서 자주 나오는 행렬에 대한 몇 가지 구현 방법을 공부해보자.

 

행렬의 표현

 

행렬의 표현은 자료구조에서 보통 2차원 배열로 표현하게 된다.

만약에 큐브라면 3차원 배열로 구현하면 된다.

//2 x 2 행렬
int a[2][2] = 
{
    {1, 1},
    {1, 1}
};

//3 x 3 행렬
int b[3][3] =
{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 2 x 5 행렬
int c[2][5] = 
{
    {1, 2},
    {3, 4},
    {5, 6},
    {7, 8},
    {9, 10}
};

행렬의 곱셈

 

"A의 행렬 x B의 행렬" 를 물어보는 문제가 간간히 등장한다.

이럴 때 행렬의 곱셈을 구현하는 방법을 따로 연습하지 않았더라면 꽤나 시간을 잡아먹을 수 있다!

 

핵심은 다음과 같다.

C의 행렬[i][j] = A의 행렬의 i 행 x B의 행렬의 j열

 

구현은 다음과 같이 할 수 있다.

#include <iostream>

using namespace std;

int main()
{
    int a[2][3] = {{1,2,3},{4,5,6}};
    int b[3][2] = {{7,8},{9,10},{11,12}};
    int c[2][2] = {{0,0},{0,0}};
    
    // 행렬의 곱셈 구현 : 시간복잡도 O(N^3)
    for(int i = 0; i < 2; i++) // a의 행
    {
        for(int j = 0; j < 2; j++) // b의 열
        {
            for(int k = 0; k < 3; k++) // a의 열 == b의 행
            {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            cout << c[i][j] << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

행렬의 회전

 

행렬의 회전하는 것도 자주 등장하는 문제 중 하나다.

시계방향인지, 반시계방향인지 생각하고 구현 방법을 배워놓으면 나중에 실수를 줄일 수 있다.

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int> > matrix;

// N x N 시계방향으로 90도 회전
matrix rotateRight(const matrix& a)
{
    int n = static_cast<int>(a.size());
    matrix ret(n, vector<int>(n, 0));
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            ret[j][n - 1 - i] = a[i][j];
        }
    }
    return ret;
}

// N x M 시계방향으로 90도 회전
matrix rotateRightOther(const matrix& a)
{
    int r = static_cast<int>(a.size());
    int c = static_cast<int>(a[0].size());
    //주의! M x N 으로 만들자.
    matrix ret(c, vector<int>(r,0));
    
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            ret[j][r - 1 - i] = a[i][j];
        }
    }
    return ret;
}

//N x N 반시계방향으로 90도 회전
matrix rotateLeft(const matrix& a)
{
    int n = static_cast<int>(a.size());
    matrix ret(n, vector<int>(n,0));
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            ret[n - 1 - j][i] = a[i][j];
        }
    }
    return ret;
}

// N x M 반시계방향으로 90도 회전
matrix rotateLeftOther(const matrix& a)
{
    int r = static_cast<int>(a.size());
    int c = static_cast<int>(a[0].size());
    matrix ret(c, vector<int>(r,0));
    
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            ret[c - 1 - j][i] = a[i][j];
        }
    }
    return ret;
}

void printMatrix(const matrix& a)
{
    int r = static_cast<int>(a.size());
    int c = static_cast<int>(a[0].size());
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}

int main()
{
    matrix a(2, vector<int>(2, 0));
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            a[i][j] = i * 2 + j;
    
    cout << "a의 회전하기 전의 모양" << endl;
    printMatrix(a);
    
    cout << "a를 시계방향으로 90도 회전" << endl;
    printMatrix(a = rotateRight(a));
    
    cout << "a를 시계방향으로 180도 회전" << endl;
    printMatrix(a = rotateRight(a));
    
    cout << "a를 시계방향으로 270도 회전" << endl;
    printMatrix(a = rotateRight(a));
    
    cout << "a를 시계방향으로 360도 회전" << endl;
    printMatrix(a = rotateRight(a));
    
    cout << "a를 반시계방향으로 90도 회전" << endl;
    printMatrix(a = rotateLeft(a));
    
    cout << "a를 반시계방향으로 180도 회전" << endl;
    printMatrix(a = rotateLeft(a));
    
    cout << "a를 반시계방향으로 270도 회전" << endl;
    printMatrix(a = rotateLeft(a));
    
    cout << "a를 반시계방향으로 360도 회전" << endl;
    printMatrix(a = rotateLeft(a));
    
    matrix b(2, vector<int>(3, 0));
    int num = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 3; j++)
            b[i][j] = num++;
    
    cout << "b의 회전하기 전의 모양" << endl;
    printMatrix(b);
    
    cout << "b를 시계방향으로 90도 회전" << endl;
    printMatrix(b = rotateRightOther(b));
    
    cout << "b를 시계방향으로 180도 회전" << endl;
    printMatrix(b = rotateRightOther(b));
    
    cout << "b를 시계방향으로 270도 회전" << endl;
    printMatrix(b = rotateRightOther(b));
    
    cout << "b를 시계방향으로 360도 회전" << endl;
    printMatrix(b = rotateRightOther(b));
    
    cout << "b를 반시계방향으로 90도 회전" << endl;
    printMatrix(b = rotateLeftOther(b));
    
    cout << "b를 반시계방향으로 180도 회전" << endl;
    printMatrix(b = rotateLeftOther(b));
    
    cout << "b를 반시계방향으로 270도 회전" << endl;
    printMatrix(b = rotateLeftOther(b));
    
    cout << "b를 반시계방향으로 360도 회전" << endl;
    printMatrix(b = rotateLeftOther(b));
    
    return 0;
}