백준 10830 - 행렬 제곱
5 minute read
문제링크
문제 설명
- 크기가 N*N인 행렬 A가 주어지고, 행렬 A를 B번 곱했을 때 각 원소를 1000으로 나눈 나머지를 출력하라
- 행렬의 각 원소는 1000보다 작거나 같은 자연수 또는 0이다.
- N은 2~5, B는 1~100,000,000,000
문제 접근 방향(bokyoung) — 틀렸습니다
- 원소 값이 1000을 넘어가면 1000으로 나눈 나머지 값만 원소에 담는다. 몫은 다룰 필요가 없기 때문에.
- 앞에서부터 2개씩 묶어서 행렬 연산을 한다. front_matrix와 back_matrix를 설정
- 남은 곱셈 횟수가 홀수
- front_matrix = front_matrix X front_matrix 이고, back_matrix = front_matrix X (updated)front_matrix
- 남은 곱셈 횟수가 짝수
- 남은 곱셈 개수가 2인 경우, return front_matrix X back_matrix
- if front_matrix == back_matrix, back_matrix = front_matrix = front_matrix X front_matrix
- if front_matrix != back_matrix, front_matrix = front_matrix X front_matrix, back_matrix = front_matrix X back_matrix
- 위 과정을 행렬 곱셈이 끝날때마다 반복한다.
원인 분석
- B=1인 경우 무한루프에 빠진다.
- B는 long long 자료형이어야 한다. int 자료형은 입력 요구사항을 만족하지 못한다.
- 행렬 곱셈 연산 횟수가 홀수일때, back_matrix를 결정하는 로직에 주의해야 한다.
구현 결과 (틀렸습니다)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int N;
// NxN 행렬곱 연산 함수
vector<vector<int>> matrix_mul(vector<vector<int>>& front_matrix, vector<vector<int>>& back_matrix)
{
vector<int> row, col;
vector<vector<int>> new_matrix(N, vector<int>(N));
for (int r = 0; r < N; r++)
{
// r행에 해당하는 원소를 담는다.
for (int c = 0; c < N; c++)
row.push_back(front_matrix[r][c]);
// 행렬곱을 통해 원소 값을 계산한다.
for (int c = 0; c < N; c++)
{
// row 원소와 곱할 열 원소를 담는다.
for (int r = 0; r < N; r++)
col.push_back(back_matrix[r][c]);
// row 원소와 col 원소를 곱한다.
int ele = 0;
for (int i = 0; i < N; i++)
ele += row[i] * col[i];
new_matrix[r][c] = ele % 1000;
col.clear();
}
row.clear();
}
return new_matrix;
}
bool check_matrix(vector<vector<int>>& matrix1, vector<vector<int>>& matrix2)
{
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (matrix1[r][c] != matrix2[r][c])
return false;
return true;
}
void matrix_b_square(vector<vector<int>>& front_matrix, vector<vector<int>>& back_matrix, int b)
{
// 남은 곱셈 횟수(b)가 짝수인 경우
if (b % 2 == 0)
{
if (check_matrix(front_matrix, back_matrix)) // front_matrix와 back_matrix가 같은 경우
{
front_matrix = matrix_mul(front_matrix, front_matrix);
back_matrix = front_matrix;
}
else
{
back_matrix = matrix_mul(front_matrix, back_matrix);
front_matrix = matrix_mul(front_matrix, front_matrix);
}
}
else // 남은 곱셈 횟수(b)가 홀수인 경우
{
vector<vector<int>> before_front_matrix = front_matrix;
front_matrix = matrix_mul(front_matrix, front_matrix);
back_matrix = matrix_mul(before_front_matrix, front_matrix);
}
}
void print_matrix(vector<vector<int>>& matrix)
{
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++)
cout << matrix[r][c] << " ";
cout << endl;
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int B;
cin >> N >> B;
vector<vector<int>> matrix(N, vector<int>(N));
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
cin >> matrix[r][c];
vector<vector<int>> front_matrix = matrix;
vector<vector<int>> back_matrix = matrix;
vector<vector<int>> ans_matrix = matrix_mul(front_matrix, back_matrix);
while (true)
{
if (B == 2)
{
ans_matrix = matrix_mul(front_matrix, back_matrix);
break;
}
matrix_b_square(front_matrix, back_matrix, B);
if (B == 3)
{
ans_matrix = back_matrix;
break;
}
B /= 2;
}
print_matrix(ans_matrix);
return 0;
}
개선 사항
- B=1인 경우 입력한 matrix를 그대로 출력하도록 한다.
- B를 long long 자료형으로 변경한다.
- 곱셈 연산 횟수가 홀수인 경우, back_matrix는 front_matrix X front_matrix 결과와 기존 back_matrix 행렬의 곱으로 결정이 되어야 한다. 로직에 수정이 필요했다.
구현 결과
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int N;
// NxN 행렬곱 연산 함수
vector<vector<int>> matrix_mul(vector<vector<int>>& front_matrix, vector<vector<int>>& back_matrix)
{
vector<int> row, col;
vector<vector<int>> new_matrix(N, vector<int>(N));
for (int r = 0; r < N; r++)
{
// r행에 해당하는 원소를 담는다.
for (int c = 0; c < N; c++)
row.push_back(front_matrix[r][c]);
// 행렬곱을 통해 원소 값을 계산한다.
for (int c = 0; c < N; c++)
{
// row 원소와 곱할 열 원소를 담는다.
for (int r = 0; r < N; r++)
col.push_back(back_matrix[r][c]);
// row 원소와 col 원소를 곱한다.
int ele = 0;
for (int i = 0; i < N; i++)
ele += row[i] * col[i];
new_matrix[r][c] = ele % 1000;
col.clear();
}
row.clear();
}
return new_matrix;
}
bool check_matrix(vector<vector<int>>& matrix1, vector<vector<int>>& matrix2)
{
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (matrix1[r][c] != matrix2[r][c])
return false;
return true;
}
void matrix_b_square(vector<vector<int>>& front_matrix, vector<vector<int>>& back_matrix, long long b)
{
// 남은 곱셈 횟수(b)가 짝수인 경우
if (b % 2 == 0)
{
if (check_matrix(front_matrix, back_matrix)) // front_matrix와 back_matrix가 같은 경우
{
front_matrix = matrix_mul(front_matrix, front_matrix);
back_matrix = front_matrix;
}
else
{
back_matrix = matrix_mul(front_matrix, back_matrix);
front_matrix = matrix_mul(front_matrix, front_matrix);
}
}
else // 남은 곱셈 횟수(b)가 홀수인 경우
{
front_matrix = matrix_mul(front_matrix, front_matrix);
back_matrix = matrix_mul(front_matrix, back_matrix);
}
}
void print_matrix(vector<vector<int>>& matrix)
{
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++)
cout << matrix[r][c] << " ";
cout << endl;
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
long long B;
cin >> N >> B;
vector<vector<int>> matrix(N, vector<int>(N));
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
{
int val;
cin >> val;
matrix[r][c] = val%1000;
}
vector<vector<int>> front_matrix = matrix;
vector<vector<int>> back_matrix = matrix;
vector<vector<int>> ans_matrix = matrix_mul(front_matrix, back_matrix);
while (true)
{
if (B == 1)
{
ans_matrix = front_matrix;
break;
}
if (B == 2)
{
ans_matrix = matrix_mul(front_matrix, back_matrix);
break;
}
matrix_b_square(front_matrix, back_matrix, B);
if (B == 3)
{
ans_matrix = back_matrix;
break;
}
B /= 2;
}
print_matrix(ans_matrix);
return 0;
}
보완 사항
- matrix_mul() 함수 변경. 시간복잡도는 동일
vector<vector<int>> matrix_mul(vector<vector<int>>& mat1, vector<vector<int>>& mat2)
{
int n = mat1[0].size();
vector<vector<int>> rmat(N, vector<int>(N,0));
for(int r=0; r<n; r++)
{
for(int c=0; c<n; c++)
{
int ele=0;
for(int i=0; i<n; i++)
ele += (mat1[r][i] * mat2[i][c]);
rmat[r][c]=ele;
}
}
return rmat;
}
- vector 컨테이너는 == 연산자 오버로딩 지원
if(check_valid(front_matrix, back_matrix) == if(front_matrix == back_matrix)
- B가 짝수인 경우 front_mat과 back_mat이 일치하는지 확인할 필요가 없다. back_mat를 먼저 결정해주고 front_mat을 결정해주면 되기 때문에
updated source code
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> matrix_mul(vector<vector<int>>& front_mat, vector<vector<int>>& back_mat)
{
int n = front_mat[0].size();
vector<vector<int>> rmat(n, vector<int>(n,0));
for(int r=0; r<n; r++) {
for(int c=0; c<n; c++) {
int ele=0;
for(int i=0; i<n; i++) {
ele += front_mat[r][i]*back_mat[i][c];
}
rmat[r][c] = ele%1000;
}
}
return rmat;
}
void print_matrix(vector<vector<int>>& mat)
{
int n = mat[0].size();
for(int r=0; r<n; r++) {
for(int c=0; c<n; c++)
cout << mat[r][c] << " ";
cout << endl;
}
}
void pow_matrix(vector<vector<int>>& front_mat, vector<vector<int>>& back_mat, long long B)
{
// B가 1인 경우 그대로 출력
if(B==1) {
print_matrix(front_mat);
return;
}
int n = front_mat[0].size();
vector<vector<int>> ans_mat(n, vector<int>(n,0));
while(B>=2) {
if(B%2==0) { // 짝수인 경우
back_mat = matrix_mul(front_mat, back_mat);
front_mat = matrix_mul(front_mat, front_mat);
}
else { // 홀수인 경우
front_mat = matrix_mul(front_mat, front_mat);
back_mat = matrix_mul(front_mat, back_mat);
}
ans_mat = back_mat;
B/=2;
}
print_matrix(ans_mat);
}
int main()
{
int N;
long long B;
cin >> N >> B;
vector<vector<int>> front_matrix(N,vector<int>(N,0));
vector<vector<int>> back_matrix(N,vector<int>(N,0));
for(int r=0; r<N; r++)
for(int c=0; c<N; c++) {
int val;
cin >> val;
front_matrix[r][c] = val%1000;
}
back_matrix = front_matrix;
pow_matrix(front_matrix, back_matrix, B);
return 0;
}
Leave a comment