🍣 Fibonacci Sequence

🍣 유명하고 유명한 피보나치 수열(Fibonacci Sequence)은 아래와 같이 표현할 수 있다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...

① Recursive Definition

🍣 즉, Fn을 n번째 피보나치 수라고 한다면 재귀 방식으로 Fn을 아래와 같이 표현할 수 있다.

 

F(n) = F(n-1) + F(n-2)

with initial conditions F(0) = 0 and F(1) = 1

 

: 즉, Fn을 구할 때 Fn-1과 Fn-2를 사용해 재귀적 호출로 Fn을 정의할 수 있다. Fn을 재귀적으로 구하는 알고리즘의 시간복잡도는 O(2^n). Fn 호출에 동일 재귀함수 두 번을 호출하기 때문.

n=int(input())

def get_fibonacci(n):
    if n==1:
        return 1
    elif n==0:
        return 0
    else:
        return get_fibonacci(n-2)+get_fibonacci(n-1)

if n>=2:
    print(get_fibonacci(n))
else:
    if n==0: print(0)
    else: print(1) #n==1

② Memoization DP technique

🍣 위 ① 재귀 호출의 결정적인 단점은 바로 중복 호출되는 Fx(0<=x<N)이 너무 많다는 점. 따라서 시간복잡도를 따졌을 때 비효율적이다. 예를 들어 F8을 구하고자 할 때, F7 따로, F6따로 호출된다. 그리고 F7에서 또 F6과 F5가 호출되는데, 이 때 F6이 두번이나 호출됨을 알 수 있다.

 

🍣 중복호출되는 Fx의 단점을 보완하기 위해 Fx(0<=x<N)가 각각 최대 2번만 호출될 수 있게 시간 복잡도 O(N)으로 풀 수 있다. 메모이제이션 테크닉을 활용해, 아래와 같이 저장된 메모리의 값을 활용해나가면 된다.

: 앞선 두 숫자를 활용해서 새로운 숫자를 구해나가는 방식으로(memoization DP) 진행한다. 그러면 맨 앞 숫자 0과 나 자신 및 나 자신 앞의 숫자를 제외하고, 그 사이의 모든 숫자는 각각 두 번만 호출. 따라서 시간복잡도는 대략적으로 O(2N)이라 할 수 있으므로 시간복잡도는 O(N)

③ Pisano Period

🍣 피보나치 수를 m으로 나눈 나머지는 주기를 이룬다는 사실을 활용. k(m)을 반복하는 부분 수열의 길이라고 하면 k(m)과 관련한 여러 성질이 존재한다.

 

🍣 일단 피사노 주기는 모든 m에 대해 존재한다. 즉, m으로 나눈 나머지의 수열은 주기를 나타낸다.

→ Fn%m을 구한 뒤, (F(n-1)%m, F(n)%m)은 비둘기집의 원리에 의해 m^2 경우의 수에 무조건 포함. 따라서, 비둘기집의 원리에 의해 (F(n-1)%m, F(n)%m)은 최대 m^2개가 존재하며, 이는 곧 (m^2+1)번째의 pair (F(n-1)%m, F(n)%m))는 앞선 pair 중 적어도 1개 이상의 pair와 중복됨을 알 수 있다. 이를 통해 피사노 주기는 무조건 존재함을 알 수 있고, k(m)은 최대 m^2+1이하임을 알 수 있다.

 

ex) mod 10에서 앞의 수와 짝을 이루어 (0,0) ~ (0,9) / (1,0) ~ (1,9) ~ 와 같이 총 10^2의 100가지 경우의 수 존재. 따라서 피사노 주기 k(10)의 최댓값은 101이다. F1과 F2는 1, 1이므로 1, 1이 나올 때 멈춰서 피사노 주기를 구하면 된다.

 

ex) mod 11 예시(k(11) = 8) : 그림 출처: BOJ 9471

 

: 피보나치 수열의 모든 원소를 mod m으로 진행한 결과에서, 피사노 주기의 길이를 k(m)라고 한다면 아래와 같이 피사노 주기 관련 7개의 성질이 알려져 있다.

(1) m>2인 경우 k(m)은 짝수

(2) 임의의 짝수 정수 n>2에 대해서 k(m) = n인 m이 항상 존재

(3) k(m)<=m^2-1

(4) k(2^n)=3x2^(n-1)

(5) k(5^n)=4x5^n

(6) k(2x5^n)=6n

(7) n>=2라면 k(10^n) = 15x(10^(n-1))

④ Power by Divide & Conquer (Matrix) technique

🍣 위 ①과 ②에서 설명한 방법과 달리, '거듭제곱을 활용한 분할정복'으로 더 빠른 시간복잡도로 피보나치 수를 구할 수 있다.

F(n+2) = F(n+1) + F(n)

F(n+1) = F(n) + F(n-1)

: 위 두 식을 행렬을 활용해서 나타내면 아래와 같다.(n>=2)

 

: 위 식을 Fn(n>=1)에 관해 연쇄적으로 (1 1 1 0) 2x2 행렬을 곱하면 아래와 같다.

 

: 즉, Fn을 구하기 위해서는 (1 1 1 0) 2x2 행렬을 n-1번 제곱하면 된다. 이 때 Power by Divide & Conquer 테크닉을 활용해 O(log(n-1)), 즉 O(logn)으로 Fn을 구할 수 있다. (1 1 1 0) 2x2 행렬을 n-1번 제곱한 뒤 왼쪽 상단 원소([0][0])가 Fn.

n=int(input())
BIG = 1_000_000_007

def get_power(a,b,c):
    if b <= 1:
        return [[a[0][0]%BIG,a[0][1]%BIG],[a[1][0]%BIG,a[1][1]%BIG]]
        
    x = get_power(a,b//2,c)

    if b % 2 == 0:
        return prod(x,x)
    else:
        return prod(prod(x,x),a)

def prod(A,B):
    a,b,c,d=A[0][0],A[0][1],A[1][0],A[1][1]
    e,f,g,h=B[0][0],B[0][1],B[1][0],B[1][1]
    return [[(a*e+b*g)%BIG,(a*f+b*h)%BIG],[(c*e+d*g)%BIG,(c*f+d*h)%BIG]]

core = [[1,1],[1,0]]

matrix = get_power(core,n-1,BIG)

print(matrix[0][0]%BIG)

 

🍣 두 행렬 A와 B의 곱(2x2 행렬)의 결과 행렬을 출력하는 prod() 함수 생성

 

🍣 Fn은 core 행렬을 n-1 제곱한 2x2 행렬의 왼쪽 상단 원소([0][0])임을 알고, n-1 제곱을 divide & conquer기법으로 진행

① a의 b승에서 b가 1이하일 때 a 자체를 출력

② a의 b승에서 b가 1보다 클 때 b가 짝수일 경우 b//2한 get_power() 결과를 x라고 하면 prod(x,x) / b가 홀수일 경우 prod(prod(x,x),a)

→ 단순 곱이 아닌 행렬 곱이므로 prod()함수 사용만 주의

 

🍣 다만, 피보나치 수가 매우 커질 수 있으므로 큰 수를 나눈 나머지를 구하는 문제로 출제. modulo operation 성질 활용해서 도중도중 구한 나머지를 곱/더하기 자유롭게 해주면 됨.

⑤ Sigma Fibonaccis

🍣 피보나치 관련 여러 sigma 합 형태는 다양한 성질을 가진다. 

(1) F1~Fn까지의 n개의 피보나치 수의 합

 = F(n+2) - 1

---

(증명)

(2) F1~Fn까지의 홀수번째의 피보나치 수의 합

= n이 홀수일 경우 F(n+1), n이 짝수일 경우 F(n)

---

(증명)

(3) F1~Fn까지의 짝수번째의 피보나치 수의 합

= n이 짝수일 경우 F(n+1) - 1, n이 홀수일 경우 F(n) - 1

---

(증명)

(4) F1~Fn까지의 모든 피보나치 수의 제곱의 합

= F(n) x F(n+1)

---

(증명)

Exercises

★ <BOJ B2 10870 피보나치 수 5> ★ [① Recursive Defintion 활용]

: 최대 20번째의 피보나치 수를 구하는 문제. 전형적인 재귀 호출을 사용해 O(2^n)으로 구현.

 

★ <BOJ B2 2747 피보나치 수> ★ [② Memoization DP Technique 활용]

: O(n)을 활용해 memoization DP technique으로 최대 45번째의 피보나치 수를 구하는 문제

 

★ <BOJ B1 2748 피보나치 수 2> ★ [② Memoization DP Technique 활용]

: 위 2747번 문제와 동일. 최대 90번째의 피보나치 수를 구하는 문제

 

★ <BOJ B1 4150 피보나치 수> ★ [② Memoization DP Technique 활용]

: 위 2747과 똑같이 동일. 다만, 큰 수 연산 지원하는 python에서 정석대로 쉽게 풀 수 있다.

 

★ <BOJ S5 10826 피보나치 수 4> ★ [② Memoization DP Technique 활용]

: 2748번 문제와 동일하게 memoization DP technique 활용. 최대 10,000번째의 피보나치 수를 구하는 문제, 파이썬에서는 큰 수의 연산도 모두 가능하나, DP technique 사용 시 메모리 절약을 위해 앞선 두 수의 공간만 메모리 만들고 한정된 메모리 공간에서 피보나치 수 update하는 방식으로 진행.

 

★ <BOJ S3 9711 피보나치> ★ [② Memoization DP Technique 활용]

: 역시 동일하게 O(n)으로 DP technique 활용하면 되지만, 메모리 초과 주의해 두 개의 수만 선언해서 update하는 방식으로 dp-table update. modular operation property(addition) 활용하면 좀 더 빠르게 풀 수 있다.

 

★ <BOJ S4 15624 피보나치 수 7> ★ [② Memoization DP Technique 활용]

: 역시 동일하게 O(n)으로 풀림. modular operation과 DP 메모리 절약 위한 두 개 변수만 선언 테크닉 활용

 

★ <BOJ S4 9471 피사노 주기> ★ [③ Pisano Period]

: mod m이 주어졌을 때 brute-force를 활용해 피사노 주기 k(m)을 구하는 문제(mod m이 (1,1)이 나올 때 멈춰서 주기 k(m) 구하기)

 

★ <BOJ G2 2749 피보나치 수 3> ★ [③ Pisano Period의 성질 (7) 활용]

: 최대 1000_000_000_000_000_00번째의 피보나치 수를 구하는 문제. 매우 큰 수가 나올 수 있으므로 1_000_000으로 나눈 나머지를 구하는 문제. 피사노 주기 성질, 그리고 divisor가 10^k이라면 Pisano Period pi(n) = 15 x 10^(k-1)을 이용해서 푸는 문제(위 포스팅 내용 ③의 (7))

 

★ <BOJ G2 11444 피보나치 수 6> / <G2 7677 Fibonacci>★ [④ Power by Divide & Conquer Technique 활용]

: 최대 1_000_000_000_000_000_000번째의 피보나치 수 큰 수로 나눈 나머지를 구하는 문제. O(N)이 아닌 행렬 분할정복 거듭제곱을 활용한 O(logN)만 허용.

 

★ <BOJ G1 2086 피보나치 수의 합> ★ [④ Power by Divide & Conquer Technique + ⑤-(1) 활용 ]

: fibonacci sequence의 a번째 항부터 b번째 항까지의 합을 구하는 문제. b번째 항까지의 합에서 (a-1)번째 항까지의 합을 빼면 된다. b==a일 경우 단순히 F(b) 출력. 이 때 피보나치 합 공식 위 ⑤-(1) 활용해 b번째 항까지의 합은 F(b+2)-1, (a-1)번째 항까지의 합은 F(a+1)-1 연산. F(x)를 구하는 시간복잡도는 O(logn) 이하의 power by divide & conquer 활용

 

★ <BOJ G2 11442 홀수번째 피보나치 수의 합> [④ Power by Divide & Conquer Technique + ⑤-(2) 활용 ]

: 위 ⑤-(2) 활용해 n이 홀수일 경우는 F(n+1), 짝수일 경우는 F(n)을 O(logn)만에 출력

 

★ <BOJ G2 11443 짝수번째 피보나치 수의 합> [④ Power by Divide & Conquer Technique + ⑤-(3) 활용 ]

: 위 ⑤-(3) 활용해 n이 홀수일 경우 F(n)-1, 짝수일 경우 F(n+1)-1을 O(logn)만에 출력(이 때 -1이므로 mod 결과 음수 되는 경우 고려)

 

★ <BOJ P5 11440 피보나치 수의 제곱의 합> [④ Power by Divide & Conquer Technique + ⑤-(4) 활용 ]

: 위 ⑤-(4) 활용해 F(n) x F(n+1)을 각각 O(logn)만에 출력