본문 바로가기

프로그래밍

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

안녕하세요 asbear입니다. ^^ 10년간 변함없이 곰같은 블로그에 방문해 주셔서 늘 감사합니다!
[해외취업 첫걸음, 꿈이 현실로!]로 오셔서 그룹에 조인 하시면 저와 소통 하실 수 있습니다.
또한 제가 지난달부터 해외취업 전문 블로그 포쉬포우 in 런던(https://poshpaws.tistory.com) 을 함께 운영하고 있습니다. 개발자와 디자이너의 영국취업 스토리와 좀더 전문적인 칼럼 글도 연재 하고 있으며 진로상담과 전문 컨설팅도 제공합니다. 해외 취업에 관심이 있는 분들의 방문을 기다립니다!

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


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

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


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

1
2
3
4
5
6
7
8
9
10
11
unsigned fib_itr(unsigned n) {
    if (n == 0return 0;
    unsigned previous = 0;
    unsigned current = 1;
    for (unsigned i = 1; i < n; ++i) {
        unsigned next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}
cs


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

1
2
3
4
5
6
7
8
9
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];
}
cs


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
    };
};
 
cs


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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);
}
 
cs