[알고리즘] 분할정복: 피보나치 수열 빠르게 찾기

분할 정복 알고리즘의 또 다른 예제로 행렬의 거듭제곱(Matrix Exponentiation)을 사용할 수 있습니다. 이는 특히 코딩 테스트에서 종종 사용되는 주제입니다. 행렬의 거듭제곱을 이용하면 피보나치 수열 등의 문제를 빠르게 해결할 수 있습니다.

문제 설명

피보나치 수열의 n번째 숫자를 구하는 문제를 해결하기 위해 분할 정복을 이용한 행렬의 거듭제곱을 사용해보겠습니다. 피보나치 수열은 다음과 같이 정의됩니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n >= 2

행렬의 거듭제곱을 이용하면 O(log n) 시간에 피보나치 수열의 n번째 숫자를 구할 수 있습니다.

행렬의 거듭제곱을 이용한 피보나치 수열

피보나치 수열을 행렬의 곱셈으로 표현할 수 있습니다:

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

위 행렬을 A라고 할 때, n번째 피보나치 수는 A^n을 계산한 후 첫 번째 원소로 구할 수 있습니다.

파이썬 코드 구현

import numpy as np

def matrix_mult(A, B):
    # 두 행렬 A와 B의 곱셈을 반환
    return np.dot(A, B)

def matrix_power(matrix, n):
    # 행렬의 거듭제곱을 계산
    result = np.eye(len(matrix), dtype=int)  # 단위 행렬
    base = matrix

    while n > 0:
        if n % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        n //= 2

    return result

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    F = np.array([[1, 1], [1, 0]], dtype=int)
    result = matrix_power(F, n-1)

    return result[0][0]

# 예제 실행
n = 10
print(f"피보나치 수열의 {n}번째 숫자: {fibonacci(n)}")

코드 설명

1. matrix_mult 함수:

   • 두 행렬 A와 B를 곱셈합니다.

2. matrix_power 함수:

   • 행렬의 거듭제곱을 계산합니다. 거듭제곱 계산을 위해 분할 정복 기법을 사용합니다.
   • n이 홀수일 때와 짝수일 때를 구분하여 처리합니다.

3. fibonacci 함수:

   • n이 0이거나 1일 때는 직접 결과를 반환합니다.
   • 그 외의 경우 행렬 (\begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix})의 (n-1) 거듭제곱을 계산하여 첫 번째 원소를 반환합니다.

결과

피보나치 수열의 10번째 숫자는 55입니다. 이 코드는 분할 정복을 이용한 행렬의 거듭제곱으로 빠르게 계산할 수 있습니다.