[programmers] 피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

Idea

이번 문제는 백준의 01타일문제를 풀때 공부했던 방법으로 풀어보았습니다.
01타일 문제를 풀때 설명하지 않았어서, 제가아는대로 설명을 해보려고 합니다!!

Code

def solution(n):
    def matrix_mult(A, B):
        temp = [[0] * 2 for _ in range(2)]
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    temp[i][j] += (A[i][k] * B[k][j])
        for i in range(2):
            for j in range(2):
                temp[i][j] %= 1234567
    
        return temp

    def matrix_pow(n, M):
        if n == 1:
            return M
        if n % 2 == 0:
            temp = matrix_pow(n//2, M)
            return matrix_mult(temp, temp)
        else:
            temp = matrix_pow(n-1, M)
            return matrix_mult(temp, M)

    A = [[1, 1], [1, 0]]
    # print(matrix_pow(n-1, A)[0][0])
    return matrix_pow(n-1, A)[0][0]

Explain

Matrix Exponentiation을 이용한 방법이며, 관련 자료는 아래 Reference에 있습니다.
해당 방법으로 하면 시간 복잡도를 O(log n) 까지 줄일 수 있어 다루는 숫자의 범위가 커질수록 매우 큰 효율을 나타냅니다.

위의 수식을 간단한 코드로 구현해보자면 아래와 같습니다.

import numpy as np
def solution(n):
    return (np.matrix("1 1; 1 0", dtype=np.object)**n).item(1) % 1234567

설명을 거창하게 하고 싶지만, 사실 위의 코드처럼 제곱을 해준다라는게 끝입니다….

다른 풀이 #1
python다운 코드네요 ㅎㅎ

def solution(n): 
    a,b = 0,1
    for i in range(n):
        a,b = (b% 1234567),((a+b)% 1234567)
    return a 

References

• https://www.geeksforgeeks.org/matrix-exponentiation/
• https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/?ref=lbp
• https://myjamong.tistory.com/305