[알고리즘 Deep Dive #6] 피보나치로 배우는 알고리즘 최적화: 재귀부터 O(log N)까지

들어가며

피보나치 수열은 알고리즘 최적화를 설명할 때 가장 많이 등장하는 예시다.

같은 문제를 다음과 같은 복잡도로 해결할 수 있다.

\[O(2^N) \rightarrow O(N) \rightarrow O(\log N)\]

이 과정은 단순히 성능 개선을 넘어,
알고리즘 문제를 풀 때 어떤 기준으로 접근법을 선택해야 하는지를 보여준다.

피보나치를 통해 자연스럽게 다음 개념들을 배우게 된다.

• 재귀
• 메모이제이션
• 동적 계획법 (DP)
• 수학적 성질 (Pisano Period)
• 분할 정복
• 행렬 거듭제곱
• Fast Doubling

그리고 가장 중요한 원칙 하나를 얻게 된다.

문제를 풀기 전에 N의 크기를 먼저 확인한다.

---

피보나치 수열 정의

피보나치 수열은 다음과 같이 정의된다.

\[F(0)=0\] \[F(1)=1\] \[F(n)=F(n-1)+F(n-2) \quad (n\ge2)\]

초기 값은 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21 ...

이 단순한 점화식 하나가
다양한 알고리즘으로 확장된다.

문제의 핵심은 항상 이것이다.

\[F(n)=F(n-1)+F(n-2)\]

하지만 N의 크기에 따라 풀이 방식은 완전히 달라진다.

---

풀이 1: 단순 재귀 — O(2^N)

예시 문제

BOJ 2747 - N ≤ 45
BOJ 10870 - N ≤ 20

이 문제들은 입력 크기가 작다.

N ≤ 45

그래서 가장 직관적인 방법인 재귀로도 해결할 수 있다.

피보나치 정의를 그대로 코드로 옮기면 다음과 같다.

def fib(n):

    if n <= 1:
        return n

    return fib(n-1) + fib(n-2)


n = int(input())

print(fib(n))

이 방식은 수학적 정의와 거의 동일하다.

\[F(n)=F(n-1)+F(n-2)\]

하지만 이 방법에는 큰 문제가 있다.

중복 계산 문제

재귀 호출 구조를 보면 같은 계산이 계속 반복된다.

예를 들어 fib(5)를 구할 때 fib(3)이 두 번, fib(2)가 세 번 호출된다.

fib(5)
├─ fib(4)
│   ├─ fib(3)
│   │   ├─ fib(2) ← 중복
│   │   └─ fib(1)
│   └─ fib(2) ← 중복
└─ fib(3) ← 중복

재귀 트리는 대략 다음과 같은 크기로 증가한다.

\[T(n) = T(n-1) + T(n-2)\]

이는 피보나치 성장과 동일하므로

\[O(2^N)\]

정도의 시간복잡도를 가진다.

즉, N이 조금만 커져도 계산량이 폭발한다.

N	실행 가능 여부
20	매우 빠름
30	느려지기 시작
40	상당히 느림
45	거의 한계

N ≤ 45 정도가 한계다.

---

풀이 2: DP O(N)

앞서 살펴본 재귀 방식은 같은 값이 수십만 번 다시 계산되는 문제가 있었다.

BOJ 10826 - N ≤ 10,000

이 문제는

N ≤ 10,000

의 범위를 가지기 때문에 재귀로 풀면 시간초과가 발생한다.

이 문제를 해결하는 방법이 바로 DP (동적 계획법) 이다.

핵심 아이디어는 간단하다.

한 번 계산한 값은 저장하고 다시 사용한다

이 방식은 dp 포스트에서 설명했던대로 두 가지 방식이 있다.

해당 포스트에서 열심히 설명했으니 여기서는 간단히 짚고 넘어가겠다.

탑다운 (메모이제이션)

재귀 구조를 유지하면서 이미 계산한 값을 저장하는 방법이다.

import sys
sys.setrecursionlimit(100000)

memo = {0: 0, 1: 1}

def fib(n):
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(int(input())))

바텀업 (테이블)

DP에서는 보통 테이블을 아래에서부터 채우는 방식을 더 많이 사용한다.

n = int(input())
dp = [0] * (n + 1)

if n >= 1:
    dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

N ≤ 10,000이면 피보나치 수 자체가 매우 커지므로 Python의 큰 정수 연산을 그대로 활용한다.

시간복잡도

DP 방식의 시간복잡도는

\[O(N)\]

이다.

재귀 방식과 비교하면

방법	시간복잡도
재귀	\(O(2^N)\)
DP	\(O(N)\)

성능 차이가 매우 크다.

---

풀이 3: 피사노 주기 — O(\pi(M))

BOJ 2749 - N ≤ 10^18, mod 1,000,000

N이 10^18이면 O(N) DP도 불가능하다. 여기서 피사노 주기(Pisano Period) 를 활용한다.

피사노 주기란?

피사노 주기

피보나치 수열을 어떤 수 $M$으로 나눈 나머지를 보면
값이 주기적으로 반복된다.

즉 다음이 성립한다.

\[F(n) \bmod M = F(n \bmod \pi(M)) \bmod M\]

여기서

\[\pi(M)\]

를 피사노 주기라고 한다.

예를 들어

\[F(n) \bmod 10\]

을 계산하면 다음과 같이 반복된다.

F(N) mod 10:
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, [0, 1, ...] → 반복 시작

이 경우 주기는

\[60\]

이다.

따라서

\[F(1000) \bmod 10\]

은 실제로는

\[F(1000 \bmod 60)\]

만 계산하면 된다.

다른 예시를 보자.

mod = $10^6$ 인 경우

이 문제에서는

\[M = 10^6\]

이다.

이때 피사노 주기는 다음과 같다.

\[\pi(10^6) = 1{,}500{,}000\]

따라서

\[F(n) \bmod 10^6\]

은

\[F(n \bmod 1{,}500{,}000)\]

만 계산하면 된다.

즉 문제 크기가

\[10^{18}\]

에서

\[1{,}500{,}000\]

으로 줄어든다.

---

피사노 주기 직접 구하기

앞에서는 이미 알려진 값을 사용했다.

\[\pi(10^6) = 1{,}500{,}000\]

하지만 일반적으로는 피사노 주기를 직접 계산할 수도 있다.

피보나치 수열을 mod $M$으로 계산하다가

\[(0,1)\]

패턴이 다시 등장하면 주기가 시작된 것이다.

즉, 아래와 같이 구현할 수 있다.

def pisano_period(m):

    a, b = 0, 1

    for i in range(m * m):

        a, b = b, (a + b) % m

        if a == 0 and b == 1:
            return i + 1


m = 1000000

print(pisano_period(m))

---

왜 (0,1)을 찾는가

피보나치 수열은 항상 다음 두 값으로 시작한다.

\[F(0) = 0\] \[F(1) = 1\]

따라서 수열이 다시 (0,1) 상태로 돌아오면
그 이후 값들도 동일하게 반복된다.

즉 그 지점이 바로 주기의 시작점이다.

---

구현

def pisano(m):
    a, b = 0, 1
    for i in range(m * m):
        a, b = b, (a + b) % m
        if a == 0 and b == 1:
            return i + 1

def fib_mod(n, m):
    period = pisano(m)
    n = n % period
    a, b = 0, 1
    if n == 0:
        return 0
    for _ in range(n - 1):
        a, b = b, a + b
    return b % m

n = int(input())
print(fib_mod(n, 1000000))

---

시간복잡도

피사노 주기의 상한은 다음과 같다.

\[\pi(M) \le M^2\]

하지만 실제로는 훨씬 작다.

예를 들어

\[\pi(10^6) = 1{,}500{,}000\]

이므로 충분히 빠르게 계산할 수 있다.

---

풀이 4: 행렬 거듭제곱 O(log N)

앞 문제에서는 mod가 $10^6$로 고정되어 있어서
피사노 주기를 사용할 수 있었다.

BOJ 11444 - N ≤ 10^18, mod 1,000,000,007

하지만 위 문제처럼

N ≤ 10^18
mod = 1,000,000,007

mod값이 큰 경우에는 피사노 주기를 적용하기 어렵다.

피사노 주기는 mod가 작거나 특정한 경우에는 매우 강력하지만,
mod가 $10^9$ 수준으로 커지면 시간초과가 발생한다.

이때 사용하는 방법이 바로 행렬 거듭제곱(Matrix Exponentiation) 이다.

핵심 아이디어

피보나치 점화식

\[F(n)=F(n-1)+F(n-2)\]

은 다음과 같이 행렬로 표현할 수 있다.

\[\begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix}\]

이를 반복 적용하면 다음 관계가 성립한다.

\[\begin{pmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}\]

즉,

행렬을 n제곱하면 $F(n)$을 구할 수 있다.

---

빠른 거듭제곱 (Fast Exponentiation) - O(log N)

행렬을 단순히 $n$번 곱하면

\[O(N)\]

이 된다.

대신 분할 정복을 사용한다.

예를 들어

\[M^8\]

은 다음과 같이 계산할 수 있다.

\[M^8=(M^4)^2\] \[M^4=(M^2)^2\] \[M^2=M \times M\]

즉 필요한 곱셈 횟수는

\[O(\log N)\]

이 된다.

---

구현

import sys
input = sys.stdin.readline

MOD = 1_000_000_007

def mat_mul(A, B):
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD]
    ]

def mat_pow(M, n):
    # 단위 행렬
    result = [[1, 0], [0, 1]]
    while n:
        if n & 1:
            result = mat_mul(result, M)
        M = mat_mul(M, M)
        n >>= 1
    return result

n = int(input())
if n == 0:
    print(0)
else:
    M = [[1, 1], [1, 0]]
    print(mat_pow(M, n)[0][1])

---

왜 [0][1]이 답인가

행렬 공식에 따르면

\[\begin{pmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{pmatrix}\]

이 되므로

\[[0][1] = F(n)\]

이다.

시간복잡도: 왜 O(log N)인가?

---

시간복잡도

행렬 곱은 상수 시간이고
거듭제곱 횟수는 다음과 같다.

\[\log_2(10^{18}) \approx 60\]

즉 약 60번 정도의 계산만으로 결과를 구할 수 있다.

---

풀이 5: Fast Doubling (행렬 없이 O(log N))

행렬 거듭제곱을 더 단순한 형태로 정리하면
다음 공식이 등장한다.

\[F(2k)=F(k)(2F(k+1)-F(k))\] \[F(2k+1)=F(k)^2+F(k+1)^2\]

이 공식을 이용하면 행렬 없이도

\[O(\log N)\]

에 계산할 수 있다.

이 방법을 Fast Doubling 이라고 한다.

---

핵심 아이디어

핵심 아이디어는 다음과 같다.

n을 절반으로 나누면서 계산한다

즉

\[F(n)\]

을 계산하기 위해

\[F(\lfloor n/2 \rfloor)\]

만 알면 된다.

그래서 전체 시간복잡도는

\[O(\log N)\]

이 된다.

---

구현

import sys
input = sys.stdin.readline

MOD = 1_000_000_007

def fast_doubling(n):
    if n == 0:
        return 0, 1  # F(0), F(1)
    a, b = fast_doubling(n >> 1)
    c = a * (2*b - a) % MOD
    d = (a*a + b*b) % MOD
    if n & 1:
        return d, (c + d) % MOD
    return c, d

n = int(input())
print(fast_doubling(n)[0])

행렬 없이 두 값만 유지하므로 구현이 더 간단하다.

---

특징

Fast Doubling은 다음과 같은 장점이 있다.

• 시간복잡도:

\[O(\log N)\]

• 행렬 연산이 필요 없다
• 코드가 더 짧다

그래서 실제로는 행렬 거듭제곱보다 이 방법을 더 많이 사용한다.

---

N 크기별 풀이 선택

피보나치 문제는 입력 크기에 따라 사용하는 알고리즘이 완전히 달라진다.

다음 표는 일반적으로 사용하는 기준이다.

N 범위	사용 알고리즘	시간복잡도
N ≤ 45	재귀	\(O(2^N)\)
N ≤ 10,000	DP	\(O(N)\)
N ≤ \(10^{18}\), mod가 작음	Pisano Period	\(O(\pi(M))\)
N ≤ \(10^{18}\), mod가 큼	Matrix / Fast Doubling	\(O(\log N)\)

예를 들어

• BOJ 10870 → 재귀 가능
• BOJ 10826 → DP
• BOJ 2749 → Pisano Period
• BOJ 11444 → Matrix / Fast Doubling

같은 피보나치 문제라도 N의 크기와 mod 조건에 따라 접근 방법이 달라진다.

문제를 풀 때 가장 먼저 해야 할 일은 항상 이것이다.

1️⃣ 입력 크기 확인
2️⃣ 가능한 시간복잡도 계산
3️⃣ 그에 맞는 알고리즘 선택

---

정리

피보나치 수열은 단순해 보이지만
알고리즘 최적화의 핵심 개념들이 모두 담겨 있다.

같은 문제라도 접근 방법에 따라 시간복잡도는 크게 달라진다.

\[O(2^N) \rightarrow O(N) \rightarrow O(\log N)\]

이 과정에서 우리는 다음을 배울 수 있다.

• 재귀 호출의 한계
• 중복 계산을 제거하는 DP
• 수학적 성질을 이용한 Pisano Period
• 분할 정복을 이용한 행렬 거듭제곱
• 행렬을 단순화한 Fast Doubling

결국 알고리즘 문제에서 가장 중요한 것은 이것이다.

문제를 풀기 전에 N을 먼저 본다

입력 크기가 작다면 단순한 방법이 가장 빠르고,
입력 크기가 커질수록 더 효율적인 알고리즘이 필요하다.

피보나치 문제는
“입력 크기에 맞는 알고리즘을 선택하는 감각”을 기르기에 가장 좋은 예시다.

---

Tags: #알고리즘 #피보나치 #동적계획법 #재귀 #행렬거듭제곱 #FastDoubling #피사노주기 #시간복잡도 #백준 #코딩테스트 #Python #Algorithm