문제
자연수 N이 주어졌을 때, 피보나치 수를 행렬 거듭제곱으로 빠르게 구하라. (코드는 피보나치 행렬 거듭제곱 구현)
입력
자연수 N이 주어진다.
출력
피보나치 수 F(N)을 1,000,000으로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 | 55 |
풀이
2x2 피보나치 행렬 [[1,1],[1,0]]을 N+1번 거듭제곱하면 결과 행렬의 [-1][-1] 위치에 F(N)이 들어간다. 분할 정복으로 행렬 곱셈을 수행하여 O(log N)에 계산한다.
- 피보나치 행렬
[[1,1],[1,0]]을 정의한다 - 분할 정복으로 행렬 거듭제곱을 수행한다: 짝수면 절반씩 곱하고, 홀수면 원래 행렬을 한 번 더 곱한다
- 행렬 곱셈 시 각 원소를 MOD(1,000,000)로 나눈 나머지로 관리한다
- 결과 행렬의 마지막 원소를 출력한다
핵심 아이디어: 피보나치 점화식이 행렬 곱셈으로 표현되므로, 행렬 거듭제곱의 분할 정복으로 O(log N)에 계산할 수 있다.
코드
from sys import stdin
MOD = 1_000_000
def mat_mul(m1, m2):
result = [[0 for _ in range(len(m2[0]))] for _ in range(len(m1))]
for i, row in enumerate(m1):
for j, col in enumerate(zip(*m2)):
result[i][j] = sum([r * c for r, c in zip(row, col)]) % MOD
return result
def get_power_of_mat(m, power):
if power == 1:
return m
squared = get_power_of_mat(m, power // 2)
if power % 2 == 0:
return mat_mul(squared, squared)
else:
return mat_mul(m, mat_mul(squared, squared))
N = int(stdin.readline())
fibonacci_mat = [[1, 1], [1, 0]]
print(get_power_of_mat(fibonacci_mat, N + 1)[-1][-1])복잡도
- 시간: O(log N)
- 공간: O(1)