c++ 알고리즘 피보나치수 - 왜 시간초과가 뜰까?

프로그래머스 혹은 백준 알고리즘과 같은 플랙폼에서 연습문제를 풀어볼 시에, 우리는 솔루션으로 피보나치를 사용하면 풀리는 문제들을 많이 만났을 것이다. 피보나치로 풀면 되겠다고 기뻐했지만, 문제를 피보나치로 구현을 하면 답은 맞는데 계속 시간 초과가 뜨는 문제들을 만나 당황을 했던 경우가 있을 것이다. 이러한 경우에는 어떻게 해결을 할까?

 

프로그래머스의 연습문제 중 하나를 예로 가져왔다.

https://programmers.co.kr/learn/courses/30/lessons/12945

이러한 문제들은 명시적으로 피보나치라고 말을 하였기에 피보나치로 해결을 해야 한다는 것은 바로 알 수 있다. 그렇다면 우리는 구현을 int fibo(n) 혹은 long fibo(n) 과 같은 형식으로 함수로 만들어 fibo(n) = fibo(n-1) + fibo(n-2) 와 같이 구현을 하거나, main 문 안에서 바로 구현을 했을 것이다. 이러한 구현이 우리가 흔히 하는 실수인 케이스이다. 이해하기 힘든 전문용어 사용은 최소로 하겠다.

 

먼저 우리가 흔히 하는 실수 케이스를 보여준다면

 

#include <string>
#include <vector>
using namespace std;

int fibo(int n){
    if(n == 0){ return 0;} // fibo(0) 은 0 이라고 주어짐.
    if(n == 1){ return 1;} // fibo(0) 은 1 이라고 주어짐.
    else{
        if(fibo(n-1) + fibo(n-2) > 1234567)         
        {
            return (fibo(n-1) + fibo(n-2))%1234567;
			// 1234567 보다 작은 경우는 나머지 연산의 결과가 기존 값과 같으니,
            // 1234567 이상인 경우만 나머지 처리.
        }
        else
        {  
            return fibo(n-1) + fibo(n-2);
            // 아닌 경우 바로 return
        }
    }
}

int solution(int n) {
    int answer = 0;
    answer = fibo(n);
    return answer;
}

 

 

물론 결과는 성공이다. 하지만 시간에서 실패하게 될 것이다. 그 이유를 알아보자.

이러한 방식으로 문제를 접근하게 된다면 정답은 올바르게 나올 것이다. 하지만 한 번 더 생각을 할 때에 예를 들어 입력으로 7번째 피보나치수를 구하라고 한다면, fibo(3) 을 구하고 fibo(4), fibo(5), fibo(6) 을 차례로 구하면서 매 번 연산을 많은 횟수 반복을 하고 있다는 것을 알 수 있다. 4번째 피보나치를 구하기 위해 0,1,2,3 번째 피보나치 수를 차례로 연산하고, 5번째 피보나치를 구하려고 0,1,2,3,4 번째 피보나치를 또 연산하는 낭비를 하고 있다. 이런 방식은 주어지는 입력 n이 큰 수가 주어지게 된다면 수행 시간은 기하급수적으로 늘게 되는 연산이다.

 

 

이제 이 문제를 해결하는 올바른 코드를 알아보자.

 

그렇다면 우리는 n번째 피보나치 수를 구하기 위해 이전 구한 피보나치는 그저 값만 참조를 하면 되는 형식으로 해야한다(이전 피보나치들을 또 계산하는 방식 말고).

 

그러면 가장 쉬운 방법은 무엇일까

그저 길이가 3인 배열을 만들고, 0 번째에 fibo(n-2), 1 번째에 fibo(n-1), 2 번째에는 그 둘의 합을 저장하고, 2번째의 값만 가져오면 된다. 그렇다면 우리는 연산을 계속하지 않고, '이전의 연산의 결과' 만 가지고 정답을 구하게 된다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer;
    
    vector<int> fibo; // 배열을 만든다
    fibo.push_back(0); // 0번째는 0
    fibo.push_back(1); // 1번째는 1인 피보나치이다.
    
    for(int i = 2; i<= n; i++)
    {
    // 입력으로 주어지는 n 은 2 이상이라고 하였으므로 n 이 0,1 인 경우는 넣지 않았다.
        fibo[2] = fibo[0] + fibo[1];
        if(fibo[2] > 1234567)
        {
            fibo[2] = fibo[2]%1234567;
        }
        fibo[0] = fibo[1]; // 다음 연산을 위해 한 칸씩 앞으로 옮긴다
        fibo[1] = fibo[2]; // 2번 째에는 다음 연산의 값이 들어가야 하므로.
    }
    answer = fibo[2];
    return answer;
}

 

만일 n 으로 0 혹은 1 이 들어오게 된다면 그 경우에는 0, 1 을 answer 에 할당하면 된다.

오늘의 정리

피보나치 유형의 문제는  fibo(n) = fibo(n-1) + fibo(n-2);  로 접근하게 될 경우 fibo(5) 를 구하려면 fibo(4) 와 fibo(3) 의 합인 것을 인지해 fibo(4) 와 fibo(3) 을 구하게 되고, 그로 인해 또 fibo(4) 를 위해 fibo(3), fibo(2) 를 내부적으로 불필요한 연산 반복을 하고 있다는 것을 알게 되었다. 이런 식으로 n이 커질수록 이미 행한 연산을 반복적으로 또 행하게 되어 낭비가 된다는 것을 알았다. 방지하려면? 단순히 바로 이전 값을 기억만 하고 있으면 된다. 어떻게? 배열을 만들어서.