백준 10830번 C++ 풀이

문제

https://www.acmicpc.net/problem/10830

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 4

---

풀이

 빠른 행렬 거듭제곱 문제이다. 큰 틀에서는 두가지의 알고리즘이 들어간다. 분할 정복을 이용한 빠른 거듭제곱 알고리즘과 행렬곱 알고리즘이다. 분할정복을 이용한 빠른 거듭제곱 알고리즘은 전에 풀이했던 것이 있으니 다음을 참조하자. https://codejin.tistory.com/114

백준 1629번 C언어 풀이

 

행렬곱은 좀 까다로웠다. 행렬곱의 개념 복잡하다기보단, 내가 행렬을 포함한 선형대수를 공부하지 않았기에 행렬 자체가 익숙하지 않아 그렇다. 덕분에 인공지능 이론을 이해하는데 머리가 터질뻔 했었다. 행렬곱은 다음과 같이 나타낸다.

https://ko.wikipedia.org/wiki/행렬_곱셈

(m, n) 크기의 행렬 A와 (n, p) 크기의 행렬 B를 곱하여 (m, p) 크기의 새로운 행렬 C가 만들어진다. 선형대수에서도 그러는지는 모르겠지만, 적어도 인공지능을 배울때 행렬의 크기는 흔히 세로 크기부터 적기에 그렇게 표기했다. 이때 C의 i행 j열의 원소의 값은 다음과 같다.

 

행렬에 익숙하지 않은 사람(그건 바로 나)이 보기엔 이해가 잘 가지 않는다. 사진의 A와 B 행렬을 조금 더 수학적으로 나타내보자. (m, n) 크기의 행렬 A와 (n, p) 크기의 행렬 B는 다음과 같이 작성할 수 있다.

 

https://ko.wikipedia.org/wiki/행렬_곱셈

 

그리고 A와 B의 곱으로 나오는 (m, p) 크기의 행렬 C는 다음과 같다.

 

https://ko.wikipedia.org/wiki/행렬_곱셈

 

우리가 하고자 하는 것은 행렬 C의 각 원소와 행렬 A, B의 원소와의 관계를 구하고 싶다. 쉽게 설명하기 위해 크기를 줄여보자. 적당하게 A와 B 모두 (2, 2)크기로 바꿔보자.

 

이제 좀 볼만 한거 같다. 행렬곱 A*B 의 순서는 다음과 같이 이루어진다.

 

쉽게 기억하면, (앞의 행) * (뒤의 열)을 순서대로 하는 것이다. 그렇기에 행렬곱의 결과인 C를 일반화하면 다음과 같다.

https://ko.wikipedia.org/wiki/행렬_곱셈

 

각 원소의 값은 위에서 설명한 수식과 같이 줄여 쓸 수 있는 것이다.

 

그래서 (a, b) 크기의 행렬과 (b, c) 크기의 행렬을 곱하면 O(abc)의 시간복잡도를 가진다. 일반적으로는 3중 반복문을 통해 풀이할수 있다는 뜻이다. 대충 작성하면 다음과 같을 것이다.

int a = 3, b = 3, c = 3; // 얼마든지 바뀔수 있다.
int A[a][b] = {...}, B[b][c] = {...}, C[a][c] = {0,};

for(int i = 0; i < a; i++) {
	for(int j = 0; j < c; j++) {
		for(int k = 0; k < b; k++) {
			C[i][j] += A[i][k]+B[k][j];
		}
	}
}

 

뭐... 나쁘지 않다. 하지만 이 반복문은 실제로는 더 오래걸린다. 컴퓨터구조(또는 운영체제)를 배운 사람이라면 알겠지만 메모리에 접근하기 위해서는 보조기억장치인 RAM에 접근하는거보다, 아주 적은 용량인 캐시 메모리에 접근하는 것이 훨씬 빠르기 때문이다. 하지만 이 방식은 캐시히트율이 작다. 이를 개선하기 위한 방법을 설명한 글은 아래를 참조하자.

https://sosal.kr/878

Matrix multiplication와 index에 따른 속도차이

결론은 반복문의 인덱스 순서를 kij또는 ikj 순으로 작성하는 것이 캐시히트율이 높아 같은 시간복잡도를 가지는 반복문이더라도 실제 속도는 빠르다. 이를 코드에 적용하여 풀이했다.

 

마지막으로 자잘한 포인트를 몇가지 짚어보고자 한다.

• 지수의 범위는 int형을 벗어난다. 지수의 범위가 1천억까지이기 때문이다. 숫자 잘못 읽고 int로 썼다가 틀렸다.
• 문제에서는 각 원소를 1000으로 나눈 나머지를 출력해야한다. 그런데 입력으로 들어오는 원소는 1000이하의 음이 아닌 정수이다. 만약 원소가 1000이고, 지수가 1이라면, 빠른 거듭제곱시 제대로 잡아내지 못하는 경우가 존재한다. 1000을 1000으로 나눈 나머지는 0이기 때문에 0을 출력해야하는데, 자칫하면 나머지 연산을 하지 않고 넘어갈 수 있기 때문이다. 그렇기에 입력시 1000으로 모듈러 연산을 한번 해준다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
#define endl '\n'
using namespace std;
using ll = long long;

class Matrix2D {
	vector<vector<int>> mat;
	int row, col;
public:
	Matrix2D(int row = 0, int col = 0) {
		init(row, col);
	}

	void init(int row = 0, int col = 0) {
		this->row = row;
		this->col = col;
		this->mat.resize(row, vector<int>(col, 0));
	}

    Matrix2D& input() {
		for(auto& y : mat) {
			for(int& x : y) {
				cin >> x;
				x %= 1000;
			}
		}
		return *this;
    }

	Matrix2D operator*(const Matrix2D& other) {
		int r;
		Matrix2D tmp(this->row, other.col);

		for(int k = 0; k < this->col; k++) {
			for(int i = 0; i < this->row; i++) {
				r = mat[i][k];
				for(int j = 0; j < other.col; j++) {
					tmp.mat[i][j] += r * other.mat[k][j];
					tmp.mat[i][j] %= 1000;
				}
			}
		}

		return tmp;
	}

	vector<vector<int>> getData() { return mat; }

	void print() {
		for(auto& y : mat) {
			for(auto& x : y) cout << x << ' ';
			cout << endl;
		}
	}
	
	Matrix2D pow(ll a) {
		if (a == 1) return *this;

		Matrix2D tmp(pow(a / 2));

		if (a % 2 == 1) return (*this) * tmp * tmp;
		else return tmp * tmp;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int n;
	ll b;

	cin >> n >> b;
	Matrix2D(n,n).input().pow(b).print();
}

 

1퍼틀 : 지수 자료형 / 80퍼틀 : 1000 나머지 연산