[C/C++] 백준 #2749 피보나치 수 3(분할정복)

피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠.  재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다.  재귀함수를 단순하게 이용하면, 시간 복잡도가 $O({\varphi }^N)$으로 기하급수로 늘어나지만, 이를 동적 계획법 또는 포워드 프로그래밍(Forward Programming)을 사용하면, 시간 복잡도가 $O(N)$으로 급격하게 줄어들 수 있습니다.

 

하지만 이번 문제는 N 자체가 $O(N)$ 알고리즘으로 해결하기 어려운 문제입니다.  그래서 분할 정복을 사용해야 하고, 이를 이용하면 시간 복잡도를 $O(\log N)$으로 줄일 수 있습니다.  사실 시간 복잡도는 상수시간($O(1)$) 해결까지로도 줄일 수 있습니다.  하지만 상수시간을 사용하는데 있어서는 결과값이 워낙 큰 수가 나오기 때문에 문제가 있습니다.  만약 앞자리 숫자 몇개를 찾아야 한다면, 이 상수시간 알고리즘을 사용할 수도 있겠죠.

 

matrix multiplication for fibonacci numbers

 

문제의 링크는 다음과 같습니다.

https://www.acmicpc.net/problem/2749

 

이 코드는 피보나치 수열의 매우 큰 값을 효율적으로 계산하는 프로그램입니다. 특히, 피보나치 수열의 n번째 값을 구할 때 사용하는 방법 중 하나인 행렬 거듭제곱을 활용하고 있습니다. 이 방법은 시간 복잡도를 크게 줄여, 매우 큰 n에 대해서도 빠르게 계산할 수 있게 해줍니다.

주요 개념 설명

1. 피보나치 수열
   - 피보나치 수열은 다음과 같이 정의됩니다:
     - $F(0)=0$
     - $F(1)=1$
     - $F(n)=F(n-1)+F(n-2)$ (n ≥ 2)
   - 예를 들어, $F(2)=1,F(3)=2,F(4)=3$ 등이 있습니다.

2. 행렬을 이용한 피보나치 수열 계산:
   - 피보나치 수열의 특성을 행렬 곱셈으로 표현할 수 있습니다.
   - 다음과 같은 행렬을 생각해 봅시다:
     $$\left(\begin{array}{cc}F(n)& F(n-1)\\ F(n-1)& F(n-2)\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^{n-1}$$
   - 이 행렬을 이용하면, 피보나치 수열의 n번째 값을 효율적으로 계산할 수 있습니다.

3. 행렬 곱셈을 통한 빠른 계산
   - 행렬 거듭제곱을 통해 피보나치 수열의 값을 계산하는데, 이때 반복 제곱법(Exponentiation by Squaring)을 사용하여 계산 속도를 줄입니다. 이를 통해 시간 복잡도를 O(log n)으로 낮출 수 있습니다.

코드 분석:

- `mult` 함수:
  - 두 2x2 행렬의 곱을 계산하는 함수입니다. 이 함수는 행렬 곱셈 결과를 `MOD` (1000000)로 나눈 나머지로 저장합니다. 이는 매우 큰 숫자에 대해 오버플로우를 방지하기 위해 사용됩니다.

- `main` 함수:
  - n번째 피보나치 수열의 값을 계산하기 위해 행렬 거듭제곱을 수행합니다.
  - `d`는 기본 행렬 $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$을 의미합니다.
  - `r`는 단위 행렬 $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$로 초기화됩니다.
  - 입력된 n에 대해, `n-1` 번 행렬 거듭제곱을 수행하며 결과를 `r`에 저장합니다.
  - 최종적으로 `r[0]`에는 n번째 피보나치 수가 저장되며, 이를 출력합니다.

요약:
이 코드는 행렬 거듭제곱을 이용해 피보나치 수열의 n번째 항을 효율적으로 계산하는 방법을 구현한 것입니다. 이를 통해 매우 큰 n에 대해서도 빠르고 정확하게 피보나치 수를 계산할 수 있습니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2749 - Fibonacci 3
//        - by Aubrey Choi
//        - created at 2019-07-08
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>
#define MOD 1000000

//    [f(n), f(n-1)] = [ [1, 1] [1, 0] ] [f(n-1), f(n-2)]
//    [f(n), f(n-1)] = [ [1, 1] [1, 0] ]^(n-1) [1, 0]
void mult(long long a[], const long long b[])
{
    long long r0 = (a[0] * b[0] + a[1] * b[2]) % MOD;
    long long r1 = (a[0] * b[1] + a[1] * b[3]) % MOD;
    long long r2 = (a[2] * b[0] + a[3] * b[2]) % MOD;
    long long r3 = (a[2] * b[1] + a[3] * b[3]) % MOD;
    a[0] = r0, a[1] = r1, a[2] = r2, a[3] = r3;
}

int main()
{
    long long n, d[4] = {1, 1, 1, 0}, r[4] = {1, 0, 0, 1};
    scanf("%lld", &n); n--;
    while(n)
    {
        if(n&1) mult(r, d);
        n >>= 1;
        mult(d, d);
    }
    printf("%lld\n", r[0]);
}