피보나치 수 3

문제

언어

  • JavaScript

순서도

  1. 피사노 주기를 이용해서 n 번째 피보나치 수 출력

문제 풀이 step 1

  • 본 문제를 풀기 전에 백준 9471번 - 피사노 주기 문제를 풀어보는 것을 추천드립니다.
  • 피보나치 수열을 m 으로 나눈 나머지가 주기를 이룬다고 합니다. 그 주기를 피사노 주기라고 합니다.
  • 이에 관련된 포스트는 백준 9417번 - 피사노 주기 풀이 를 참고하시면 될 것 같습니다.
  • 피사노 주기를 구하는 데에는 다음과 같은 공식이 성립한다고 합니다.
    • n > 2, k(10 ^ n) = 15 * 10 ^ (n - 1)
  • 본 문제에서 m 은 1,000,000 으로 10 ^ 6 입니다. 위의 공식을 이용하면 피사노 주기는 1,500,000 이 나옵니다.
  • 피사노 주기를 구했으니, 메모이제이션 기법으로 피사노 주기까지의 피보나치 수열을 생성합니다.
  • 그리고 주어진 n 을 피사노 주기로 나머지 연산을 한 후에 그 나머지 번째 피보나치 수를 구하면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드

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

// n > 2, k(10 ^ n) = 15 * 10 ^ (n - 1)
const solution = (input) => {
	const MOD = 1000000;
	// 피사노 주기 구하기
	const pisanoPeriodLength = 15 * 100000;

	// 주어진 n 을 피사노 주기로 나머지 연산 수행
	let n = BigInt(input[0]) % BigInt(pisanoPeriodLength);

	// 메모이제이션 기법을 이용해 피사노 주기까지의 피보나치 수열 구하기
	const fibonacci = [0, 1];
	for (let i = 2; i < pisanoPeriodLength; i++) {
		fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % MOD;
	}

	// 나머지 번째의 피보나치 수 출력
	return fibonacci[Number(n)];
};

console.log(solution(input));

다른 방법의 순서도

  1. 행렬 계산을 이용해서 n 번째 피보나치 수 출력

다른 방법의 문제 풀이 step 1

  • 피보나치 수열을 행렬의 거듭제곱으로 표현할 수 있다고 합니다.
  • 행렬의 모양을 보면 바로 이해가 갑니다. 왜냐하면 피보나치 수열의 식을 그저 행렬로 옮겨놓은 것에 불과하기 때문입니다. 백준 2749번 피보나치 수 3 의 행렬 계산 식
  • 위와 같이, 행렬의 거듭제곱 형태로 바꾸면 나머지 연산을 적용할 수 있게 됩니다.
    • 왜냐하면, 곱셈은 (A x B) % MOD = (A % MOD) x (B % MOD) 과 같은 식이 성립하기 때문입니다.
  • 그리고 행렬의 거듭제곱 형태이기 때문에 백준 1629번 - 곱셈 풀이 처럼 분할 정복 기법을 이용해서 1,000,000,000,000,000,000 번째 피보나치 수도 빠르게 구할 수 있습니다.
  • 매번 문제를 반씩 나누며 작게 만들기 때문에, 이 방법의 시간복잡도는 O(logN) 이라고 할 수 있습니다.
  • 본 풀이에 대한 설명은 주석으로 작성하겠습니다.

후기

  • 피사노 주기를 사용하는 방법보다 행렬 계산을 이용하는 방법이 메모리와 시간을 훨씬 덜 사용합니다.
  • BigInt 때문에 조금 삽질을 했습니다.
    • if (n % 2n === 0n) 이게 맞고
    • if (n % 2n === 0) 이건 틀립니다.
  • 피보나치 수열을 행렬로 표현할 수 있다는 것에 정말 놀라웠습니다. 역시 수학은 서로 연결되어 있습니다.

Reference.

다른 방법의 소스 코드

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

const init = [[1], [0]];

// 거듭 제곱을 할 행렬입니다.
const base = [
	[1, 1],
	[1, 0],
];

// 이는 항등식입니다. 어떤 행렬을 곱해도, 곱한 행렬과 같은 모양의 행렬을 반환합니다.
// 재귀 함수에서 n 이 0 일때, 사용하려고 정의했습니다.
const zero = [
	[1, 0],
	[0, 1],
];

// 행렬을 계산하는 함수입니다.
const calculateMatrix = (a, b, MOD) => {
	const res = Array.from({length: 2}, () => []);

	for (let i = 0; i < a.length; i++) {
		for (let j = 0; j < b[0].length; j++) {
			res[i][j] = 0;

			// 행렬을 계산하며, 동시에 나머지 연산도 수행해줍니다.
			for (let k = 0; k < a[0].length; k++) {
				res[i][j] += (a[i][k] * b[k][j]) % MOD;
			}
		}
	}

	return res;
};

// 분할 정복 기법을 이용해서 피보나치 수열의 행렬 거듭 제곱을 반환하는 함수입니다.
const getFibonacci = (n, MOD) => {
	//	n 이 0 일때는 항등식 행렬을 반환하도록 합니다.
	if (n === 0n) return [...zero];

	// n 이 1 일때는 베이스 행렬을 반환하도록 합니다.
	if (n === 1n) return [...base];

	// n 을 반으로 나누고, 그때의 피보나치 수열의 행렬 거듭 제곱을 구합니다.
	const mid = getFibonacci(n / 2n, MOD);

	// 만약 n 이 짝수면, 반환되는 행렬 두 개를 행렬 곱셈 계산을 합니다.
	if (n % 2n === 0n) return calculateMatrix(mid, mid, MOD);

	// 만약 n 이 홀수면, 반환되는 행렬 두 개를 행렬 곱셈 계산하고, 거기에 베이스 행렬을 한번 더 곱합니다.
	return calculateMatrix(calculateMatrix(mid, mid, MOD), [...base], MOD);
};

const solution = (input) => {
	const MOD = 1000000;
	const n = BigInt(input[0]);

	// 재귀 함수를 통해서 반환한 행렬을 [[1], [0]] 을 곱해서 피보나치 수를 출력하면 정답이 됩니다.
	const resultMatrix = calculateMatrix(getFibonacci(n, MOD), [...init], MOD);
	return resultMatrix[1][0];
};

console.log(solution(input));