행렬 제곱

문제

언어

  • JavaScript

순서도

  1. dp 방식으로 주어진 행렬을 2 의 제곱씩 곱한 배열을 생성
  2. 그리디 방식으로 위에서 생성한 배열을 이용해서 2 씩 나눠가며 행렬 곱셈 연산

문제 풀이 step 1

  • 크기가 N x N 인 행렬 A 가 주어집니다.
  • 이 때, A 의 B 제곱을 구하는 문제입니다.
  • B 의 크기가 너무 커서, 선형 방법으로 계산하기에는 무리가 있습니다.
  • 그래서 2 의 제곱을 이용합니다.
  • 우선, DP 방식으로 행렬을 2 의 제곱씩 곱한 배열을 생성합니다.
    • dp[1], dp[2], dp[4], dp[8], dp[16], …
    • dp[16] = A 행렬을 16 번 곱한 배열
  • 그리고 그리디 방식으로 B 보다 작으면서 가장 큰 2 의 제곱수를 곱해가며, A 의 B 제곱을 구합니다.
    • 예를 들어, B 가 21 이라면,
    • 우선 dp[16] 을 곱하고 21 에서 16 을 빼줍니다. 그러면 B 는 5 가 됩니다.
    • 그리고 dp[4] 를 곱하고 5 에서 4 를 빼줍니다. 그러면 B 는 1 이 됩니다.
    • 마지막으로 dp[1] 을 곱하면, B 는 0 이 되고, A 의 21 제곱을 구할 수 있습니다.
  • 위와 같은 방식으로 A 의 B 제곱을 구하고 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 제가 푼 방식은 정형화된 방식이 아닙니다.
  • 본 문제를 푸는 정형화된 방식은 분할 정복 기법으로, 우선 분할 정복 기법을 공부하고 풀면 좋을 것 같습니다.
  • 그치만 역시 수학의 매력은 해답까지 가는 길이 다양하다는 것..

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 두 개의 행렬을 곱하는 함수
const squareMatrix = (n, A, B, MOD) => {
	const newMatrix = Array.from({length: n}, () => Array(n).fill(0));

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
				newMatrix[i][j] += A[i][k] * B[k][j];
			}
			newMatrix[i][j] %= MOD;
		}
	}

	return newMatrix;
};

const solution = (input) => {
	const MOD = 1000;

	let [n, b] = input[0].split(" ").map(Number);
	let matrix = input.slice(1).map((v) => v.split(" ").map(Number));

	// dp 방식을 이용해서 행렬을 2 의 제곱씩 곱한 배열을 생성
	const dp = [];
	dp[1] = matrix;
	for (let i = 2; i < 100000000000; i *= 2) {
		matrix = squareMatrix(n, matrix, matrix, MOD);
		dp[i] = matrix;
	}

	// 항등식 생성
	let res = Array.from({length: n}, () => Array(n).fill(0));
	for (let i = 0; i < n; i++) {
		res[i][i] = 1;
	}

	// 제한 내에서 가장 큰 2 의 제곱수로 초기화 (그리디 방식처럼)
	let base = 68719476736;
	while (b !== 0) {
		// b 보다 작아질 때까지 base 를 2 로 나누기
		while (base > b) {
			base /= 2;
		}

		// b 에서 base 만큼 빼주기
		b -= base;
		// dp[base] 곱하기
		res = squareMatrix(n, res, dp[base], MOD);
	}

	return res.map((v) => v.join(" ")).join("\n");
};

console.log(solution(input));