다양한 피보나치 수열 알고리즘

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

 

피보나치 수는 $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로 나눈 나머지를 리턴하는 함수를 완성하세요

 

 

2. 제한사항

 

n은 1이상, 100000이하인 자연수

 

 

3. 예시

 

n=3이면 return=2

 

n=5이면 return=5

 

피보나치 수는 0번째부터 0,1,1,2,3,5,...와 같이 이어진다

 

 

4. 나의 풀이

 

피보나치 수 하면 재귀적 알고리즘이니까…

 

def solution(n):
    
    answer = 0
    
    def fib(n):
        
        if n == 0:
            
            return 0
        
        elif n == 1:
            
            return 1
        
        else:
        
            return fib(n-1)+fib(n-2)
            
    return (fib(n) % 1234567)

 

이러면 시간초과된다..

 

n=40이면 fib(40)도 10초안에 계산을 못함

 

재귀적 알고리즘이 시간을 많이 소요한다고 했던 것 같아서

 

내가 생각할 수 있는 방법은

 

리스트에 원소를 두개씩 빼서 더해가지고 리스트에 추가하는 방식으로..

 

zero index로 피보나치 수를 세고 있으니까

 

def solution(n):
    
    answer = 0
    
    fib_list = [0,1]
    
    m = 2
    
    while m != n+1:
        
        fib_list.append(fib_list[m-2] + fib_list[m-1])
        
        m = m + 1
        
    answer = (fib_list[n] % 1234567)
    
    return answer

 

fib_list=[0,1]로 초기 리스트를 만든다

 

2번째 피보나치 수부터 구해야하니까 m=2라고 함

 

def solution(n):
    
    answer = 0
    
    fib_list = [0,1]
    
    m = 2

 

반복문을 통해서 m이 n+1이 될때까지 반복을 할건데

 

m이 n+1이 되면 반복문을 탈출을 할 것..

 

m != n일때 종료를 하면 m=n이 되는 순간에 n번째 원소를 구하지 못하고 반복문을 탈출하니까

 

m != n+1이라고 해가지고 m=n이 되더라도 종료하지 않고 n번째 원소를 구할 수 있도록 한다

 

그러니까 n번째 피보나치 수열의 값을 구할 때까지 반복을 하게 됨

 

m번째 원소 바로 이전의 두 원소를 더해서 fib_list에 추가시킨다

 

한번 반복하면 m에 1을 더함

 

while m != n+1:
        
    fib_list.append(fib_list[m-2] + fib_list[m-1])

    m = m + 1

answer = (fib_list[n] % 1234567)

return answer

 

이렇게 하면 시간을 초과하지 않고 통과를 함

 

 

 

5. 다른 풀이

 

피보나치 수열만 구할 수 있으면 되니까 피보나치 수열을 구하는 여러가지 알고리즘을 조사해봄

 

내가 했던 첫번째 재귀적인 풀이는

 

def solution(n):
    
    answer = 0
    
    def fib(n):
        
        if n == 0:
            
            return 0
        
        elif n == 1:
            
            return 1
        
        else:
        
            return fib(n-1)+fib(n-2)
            
    return (fib(n) % 1234567)

 

$O(2^{n})$으로 상당히 시간복잡도가 큼

 

-----------------------------------------------------------------------------------------------------------------------

 

두번째 방법은 위와 같이 반복문을 이용한 방법

 

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

먼저 n이 2보다 작으면… 즉 n이 0과 1이면 0번째 값은 0이고 1번째 값은 1이니까 바로 n을 return하도록 하고

 

n이 2이상인 경우에는

 

초기 원소 a=0,b=1로 주면 각각 0번째, 1번째 수이고

 

반복문을 n번 도는데

 

n=1번 돌면 a=1, b=1+0=1이 되니까 각각 1번째 2번째 수가 된다

 

n=2번 돌면 a=1, b=1+1=2가 되니까 각각 2번째 3번째 수가 된다

 

n=3번 돌면 a=2, b=1+2=3이 되니까 각각 3번째 4번째 수가 된다

 

n=4번 돌면 a=3, b=2+3=5이 되니까 각각 4번째 5번째 수가 된다

 

결국 n번 돌면 a에 n번째 피보나치 수가 들어가고 이것을 1234567로 나눈 나머지를 return

 

반복문을 n번 도는게 끝이라 시간복잡도는 $O(n)$으로 상당히 효율적인 알고리즘

-----------------------------------------------------------------------------------------------------------------------

 

내가 푼 방법이 (의도하진 않았지만) 동적계획법을 이용한 방법인데..

 

시간복잡도가 $O(n)$정도라고 함.. 근데 두번째 방법이 실제로 시간이 더 빠른듯

 

설명을 읽어보면 핵심이 피보나치 수열을 구하기 위해서 이전 피보나치 수를 이용해서 구해야하는데…

 

이전 피보나치 수 2개는 또 이전 피보나치 수 4개를 이용해서 구하고…

 

이것이 반복된단 말이지

 

근데 이전의 수들이 중복된다는게 문제임

 

그림1. 7번째 피보나치 수열의 수를 구하는 흐름

 

예를 들어 fib(7)을 구하기 위해서 fib(3)을 몇개나 사용했는지 세보면 5개임

 

만약 재귀적 풀이를 이용했다면 fib(3)이라는 함수를 5번이나 더 호출해야한다는 거

 

이렇게 중복된다는 것이 큰 문제인데

 

그렇다면 이전 문제의 값을 1번만 구하고 어딘가에 저장한

 

다음에 필요할때마다 쓰겠다는 것이 동적계획법의 핵심적인 아이디어다

 

fib(3)을 단 1번만 호출하고 어딘가에 저장해놓은 다음에 나중에 필요할때마다 쓰겠다 이거임

 

def solution(n):

    if n <2:
    
        return n
    
    fib = [0 for _ in range(n+1)]
    
    fib[1] = 1
    
    for i in range(2,n+1):
        
        fib[i] = fib[i-1] + fib[i-2]
    
    return fib[n]%1234567

 

fib라는 dynamic table을 미리 0을 채워넣어서 만들어놓고

 

fib[0]=0이고 fib[1]=1이니까 초기 설정을 한 뒤에

 

i=2부터 n까지 반복문을 돌아

 

fib[i]를 fib[i-1]+fib[i-2]로 구해서 저장을 해놓는다

 

---------------------------------------------------------------------------------------------------------------------

다음으로 일반항을 이용해서도 풀 수 있다고함

 

점화식 $$a_{n+2} = pa_{n+1} + qa_{n}$$ 을 특성방정식 $$x^{2} = px + q$$ 으로 바꿔서

 

이 방정식의 근이 $\alpha, \beta$이면 점화식의 해는 $$a_{n} = C_{1}\alpha^{n} + C_{2}\beta^{n}$$

 

초기 조건 $a_{0}, a_{1}$에 대하여 계수 $C_{1}, C_{2}$를 구할 수 있다는 사실을 이용한다.

 

그러면 피보나치수열의 일반항은 $a_{1} = 1, a_{2} = 1$일 때 $$a_{n} = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n})$$

 

def fibo(n):
    
    sqrt_5 = 5 ** (1/2)
    
    ans = 1/sqrt_5 * (((1+sqrt_5)/2)**n - ((1-sqrt_5)/2)**n)
    
    return int(ans)

 

시간복잡도가 $O(logn)$정도로 간단하면서도 가장 빠르다

 

------------------------------------------------------------------------------------------------------------------------------

 

마지막으로 행렬의 곱셈을 이용해서도 풀 수 있다고 한다

 

만약 n번째 피보나치 수를 $F_{n}$이라고 한다면 피보나치 수를 다음과 같이 행렬화할 수 있다고 한다.

 

$$\begin{pmatrix}F_{n+1} & F_{n} \\F_{n} & F_{n-1} \\\end{pmatrix}=\begin{pmatrix}1 & 1 \\1 & 0 \\\end{pmatrix}^{n}$$

 

 

위 식의 오른쪽 행렬을 n번 제곱해서 (0,1)이나 (1,0)의 원소를 구하면 된다

 

def solution(n):
    
    size = 2
    zero = [[1,0],[0,1]] #항등행렬
    base = [[1,1],[1,0]] #곱셈을 시작할 오른쪽 기본 행렬
    
    #두 정사각행렬의 곱
    def square_matrix_mul(a,b,size=size):
        
        new = [[0 for _ in range(size)] for _ in range(size)]
        
        for i in range(size):
            
            for j in range(size):
                
                for k in range(size):
                    
                    new[i][j] += a[i][k] * b[k][j]
                    
        return new
        
        #행렬의 n제곱
    def get_nth(n):
        
        matrix = zero.copy()
        
        k = 0
        
        tmp = base.copy()
        
        while 2 ** k <= n:
            
            if n & (1 << k) != 0:
                
                matrix = square_matrix_mul(matrix,tmp)
                
            k+= 1
            
            tmp = square_matrix_mul(tmp, tmp)
            
        return matrix
    
    return get_nth(n)[1][0] % 1234567

 

2의 제곱수는 2를 계속해서 곱하면 구할 수 있지만

 

더욱 효율적인 방법은 $2^1$을 구한다음에 이 결과를 제곱하여 $2^2$을 구하고

 

$2^2$을 또 제곱하여 $2^4$을 구하고… $2^4$을 또 제곱하여 $2^8$을 구하고…

 

2의 지수가 2의 제곱이 아니면 문제일 수 있지만

 

모든 자연수는 2의 제곱수의 합으로 표현할 수 있다

 

예를 들어 $2^{100}$을 구하기 위해서 100을 2의 제곱수의 합으로 표현할 수 있는데

 

100은 4와 32와 64의 합이다.

 

그래서 $2^{100}$은 $2^4$, $2^{32}$, $2^{64}$를 곱하면 된다

 

이러면 $O(log_{2} n)$으로 아주 빠르게 구할 수 있다고 한다

 

 

6. 되돌아보기

 

동적계획법이라는거 몰랐는데… 그냥 풀어버리네

 

그동안 공부한게 효과있다는 말이겠지.?

 

어떻게 하면 시간을 줄일 수 있을까?? 생각을 하면서 코딩을 하자

 

재귀함수는 시간복잡도를 상당히 늘린다

 

한번 구한 값을 어딘가에 저장해서 필요할때마다 불러 쓸 수 있다면??

 

리스트 같은데 저장해서 불러 쓰는건 사실 알게모르게 많이했단 말이지

 

예를 들면 무슨 시험볼때 factorial을 리스트에 미리 저장해놔서 필요할때 index로 불러온적 있었지… 그거랑 똑같아

 

 

7. 참고

 

https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95

피보나치 수열 알고리즘을 해결하는 5가지 방법