테크니컬 인터뷰 단골손님, 피보나치 수열 계산하기

요즘 인터뷰 질문들 훑다보니, 초반 웜업용 질문으로 피보나치 수열 값 구하는 코드가 심심치 않게 나온다. 그도 그럴것이, 연산 자체가 매우 간단하면서도 네가지 각기 다른 방법으로 작성 할 수 있기 때문이 아닌가 싶다.

첫재로, recursive 방식으로 구현한 코드.

unsigned fibo_rec(unsigned n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibo_rec(n-1)+fibo_rec(n-2);
}

둘째로, iterative 방식으로 구현한 코드.

unsigned fib_itr(unsigned n) {
    if (n == 0) return 0;
    unsigned previous = 0;
    unsigned current = 1;
    for (unsigned i = 1; i < n; ++i) {
        unsigned next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

셋째로, dynamic programming 방식으로 구현한 코드

unsigned fibo_dyna(unsigned n) {
    vector<unsigned> v;
    v.push_back(0);
    v.push_back(1);
    for(unsigned  i = 1 ; i < n  ; ++i) {
        v.push_back(v[i] + v[i-1]);
    }
    return v[n];
}

마지막으로, template generic programming 으로 구현한 코드

template<unsigned N>
struct fibo_meta {
    enum {
        value = fibo_meta<N-1>::value+fibo_meta<N-2>::value
    };
};
 
template<>
struct fibo_meta<0> {
    enum {
        value = 0
    };
};
 
template<>
struct fibo_meta<1> {
    enum {
        value = 1
    };
};
 

그런데 template은 선처리코드에 속하는지라 variable을 이용해서 참조할 수 없다. 즉, for문을 이용해서 1부터 20까지의 피보나치 수를 구하여라 하는등의 코드를 작성하는것이 불가능하다. 따라서 그러한 응용동작을 위해 다음과같은 보조기능을 가미할 수도 있다. 아래 코드에서 initFibo()가 호출되면, MAX_FIBO 만큼의 피보나치 수열 값이 벡터에 저장되어, 변수를 인덱스로 참조하여 값을 사용할 수 있도록 확장이 가능하다.

template<unsigned N>
struct fibo_meta {
    enum {
        value = fibo_meta<N-1>::value+fibo_meta<N-2>::value
    };
    // create vector for non-const usage
    static void add(std::vector<int>& dic) {
        fibo_meta<N-1>::add(dic);
        dic.push_back(value);
    }
};
 
template<>
struct fibo_meta<0> {
    enum {
        value = 0
    };
    static void add(std::vector<int>& dic) {
        dic.push_back(value);
    }
};
 
template<>
struct fibo_meta<1> {
    enum {
        value = 1
    };
    static void add(std::vector<int>& dic) {
        fibo_meta<0>::add(dic);
        dic.push_back(value);
    }
};
 
static const size_t MAX_FIBO = 20;
vector<int> fiboVector;
static void initFibo() {
    fibo_meta<MAX_FIBO>::add(fiboVector);
}