[알고리즘] 분할 정복 피보나치 - 코딩밥상

피보나치(Fibonacci) 구하는 방법

피보나치 수열이야 고등학생부터 흔하게 접했었던 수열이기에 설명을 각설하고, 이를 일반적인 방법으로 구현하고 분할 정복을 기반으로 다시 한번 구현해보겠습니다.

피보나치 수열의 정의가 다음과 같으므로 일반적인 구현은 전혀 어렵지 않습니다. 재귀 방정식을 그대로 코드로 옮길 수 있기 때문입니다.

long Fibonacci(int n){
    if(n==0) return 0;
    
    if(n==1 || n==2) return 1;
    
    return Fibonacci(n-1) + Fibonacci(n-2);
}

하지만 이 코드는 하나의 호출이 재귀 호출로 또 다른 2개를 호출 하기 때문에 O(2^n)의 성능을 나타냅니다. 이는 최악의 성능이라고 볼 수도 있죠. 20번째 피보나치를 찾기 위해선 100만 회가 넘는 재귀 호출을 해야합니다.

분할 정복기반 피보나치 수

피보나치 수의 여러 가지 성질 중 행렬에 관한 성질을 이용하면 분할 정복 방식으로 피보나치를 구할 수 있습니다.

앞서 배운 거듭 제곱의 분할 정복 방식과 굉장히 유사합니다.

'각각의 행렬을 나누고 합친다.' n번째 피보나치를 구할 때 n/2번째 피보나치 수를 찾아 제곱하면 되고, n/2번째 피보나치를 구하려면 n/4버째 피보나치 수를 제곱하면 되는것입니다.

만약 구하려는 n이 홀수이면 행렬을 하나 따로 빼주어 짝수로 만들고 과정을 계속 해주면 됩니다. 

즉 n번째 피보나치를 구하려면 최초의 행렬을 logn(밑이 2)회 제곱하면 된다는 의미입니다.

---

구현

typedef struct tagMatrix{
    long Data[2][2];
}Matrix;

Matrix Matrix_Multiply(Matrix A, Matrix B){
    Matrix C;
    
    C.Data[0][0] = A.Data[0][0]*B.Data[0][0] + A.Data[0][1]*B.Data[1][0];
    C.Data[0][1] = A.Data[0][0]*B.Data[1][0] + A.Data[0][1]*B.Data[1][1];
    
    C.Data[1][0] = A.Data[1][0]*B.Data[0][0] + A.Data[1][1]*B.Data[1][0];
    C.Data[1][1] = A.Data[1][0]*B.Data[1][0] + A.Data[1][1]*B.Data[1][1];
    
    return C;
}

Matrix Matrix_Power(Matrix A, int n){
    if(n>1){
        A = Matrix_Power(A, n/2);
        A = Matrix_Multiply(A, A);
        
        if(n&1){
            Matrix B;
            B.Data[0][0] = 1;
            B.Data[0][1] = 1;
            B.Data[1][0] = 1;
            B.Data[1][1] = 0;
            
            A = Matrix_Multiply(A, B);
        }
    }
    return A;
}

long Fibonacci(int n){
    Matrix A;
    
    A.Data[0][0] = 1;
    A.Data[0][1] = 1;
    A.Data[1][0] = 1;
    A.Data[1][1] = 0;
    
    A = Matrix_Power(A,n);
    
    return A.Data[0][1];
}