FIBONACCI_알고리즘

1. 점화식을 이용한 일반적인 방법

생각

단계1. 먼저 피보나치 수열은 앞에서도 이야기 했지만 f(n) = f(n-1) + f(n-2)로 정의된다. 

단계2. 이 식을 점화식으로 재귀함수를 만들 수있다.

함수 내용 

 - 함수 f는 n을 입력받아 n번째 피보나치수를 리턴하는 재귀함수이다.

 - n이 2 이하 라면 1을 리턴한다..

 - n이 3 이상 이라면 f(n-1) + f(n-2)를 리턴한다.

단계3. 리턴 받은 수를 2로 나눈 나머지가 0이라면 짝수 이므로 YES, 0이 아니라면 NO를 출력한다.

코드

#include <iostream>
 
// 함수 구현
// n번째 수의 피보나치 수열을 재귀적으로 반환
long long f(int n)
{
    // 기저사례 : n이 2 이하면 1반환
    if(n <= 2)
    {
        return 1;
    }
    // 점화식 f(N) = f(N-1) + f(N-2)
    return f(n-1) + f(n-2);
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    // 숫자 N
    int N = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        scanf("%d", &N);
        long long result = f(N);
        // 짝수면 YES
        if(result % 2 == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

 

결과

10
10
NO
10
NO
10
NO
20
NO
30
YES
40
NO
50
NO

답은 구했지만 위의 코드는 함수내에서 같은 함수를 2번 호출하는 재귀함수 이므로 2^n의 시간 복잡도를 가지며 매우 오랜시간이 걸린다. 

2. 캐시활용

생각

앞에서 [BOGGLEGAME_알고리즘_3] 에서 시간을 줄일때 사용했던 방법과 같은 아이디어로 시간을 절약 할 수있다.

단계1. 캐시를 저장할 수있는 배열을 정의하고 0으로 초기화한다.

단계2. 배열의  N번째 요소가 0이라는 것은 이전에 계산된적 없는 피보나치 수라는 것으로 계산하여   캐시배열에 저장한후 리턴한다.

단계3. 배열의 N번째 요소에 0이 아닌 값이 있다는 것은 한번 계산한 값이란 의미로 그 인덱스를 바로 참조하여 리턴한다.

코드

// FIBONACCI_2
 
#include <iostream>
 
// 캐시 저장 배열
long long g_CacheArr[1001] = {0,};
 
// 함수 구현
// n번째 수의 피보나치 수열을 재귀적으로 반환
long long f(int n)
{
    // 기저사례 : n이 2 이하면 1반환
    if(n <= 2)
    {
        return 1;
    }
    
    // 캐시의 해당 요소가 아직 계산되지 않은 값이라면
    // 캐시 배열에 점화식으로 계산한 값 저장
    if(g_CacheArr[n] == 0)
        return g_CacheArr[n] = f(n-1) + f(n-2);
    else// 해당요소가 이미 계산된 값이라면 캐시값 리턴
        return g_CacheArr[n];
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    // 숫자 N
    int N = 0;
    scanf("%d", &testCase);
    
    while(testCase--){
        // 캐시배열 초기화
        memset(g_CacheArr, 0, sizeof(g_CacheArr));
        scanf("%d", &N);
        long long result = f(N);
        // 짝수면 YES
        if(result % 2 == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

결과

10
10
NO
20
NO
30
YES
40
NO
50
NO
60
YES
70
NO
80
NO
90
YES
1000
NO

 

숫자가 작을때는 큰차이를 보이지 않지만 40이상만 넘어가더라도 매우 큰 차이를 확인 할 수있다.