'수열'에 해당되는 글 1건

  1. 2016.12.07 [Algorithm] 피보나치 수열에 대하여!
2016. 12. 7. 17:28

안녕하세요. 게임개발자 놀이터 입니다.


이번 포스팅에선 피보나치 수열에 대하여 정리 해보려고합니다.


피보나치 수열


피보나치 수열은 앞의 두 수 를 더해서 현재 위치의 수를 만드는 수열을 말합니다.


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...


시작 두 수 인 0, 1을 제외하고 3번째 수부터 바로 전 수 와 전 전 수의 합계를 나타내면 됩니다.


0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...


간단한 알고리즘이라서 그런지 구현 방법은 여러가지가 있습니다.


먼저 재귀함수 호출을 이용한 피보나치 수열 구현 입니다.


1
2
3
4
5
6
7
8
int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Algorithm(n - 1+ Algorithm(n - 2);
}
cs


1번째와 2번째의 값은 0과 1로 정해져있으니, 각각 0과 1을 반환하고, n의 전 값과, n의 전전 값을 더해서 리턴하는 형식을 가지고 있습니다.


간단하게 구현을 완료했지만, Algorithm 함수를 들어갈때마다 계속 n이 1인지, 2인지를 검사 하고 시작해야 하네요.


반복전인 2회 검사를 제거 하기 위해 이번엔 반복문으로 구현해봤습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
    {
        int beforevalue = 0;
        int current = 1;
 
        for(int i=1; i<n; ++i)
        {
            int temp = current;
            current += beforevalue;
            beforevalue = temp;
        }
        return current;
    }
}
cs


간단하게 재귀 함수를 호출하는 부분을 for문으로 변경해봤습니다.


current는 현재 숫자, beforevalue는 이전 숫자입니다.

다음 숫자는 현재 숫자 + 이전숫자 이므로, current와 beforevalue를 더해서 구합니다.


이것 외에 다른 방법은.. 성능상으로는 비슷하지만 코드상으로는 다른 '꼬리 재귀 함수'를 이용한 구현법이 있습니다.


1
2
3
4
5
6
7
8
9
10
int Algorithm(int n){
    return AlgorithmTail(n, 01);
}
 
int AlgorithmTail(int n, int before, int next){
    if (n == 0)
        return before;
    else
        return AlgorithmTail(n - 1, next, before + next);
}
cs


구하려는 n번째 자리수를 이용하여 n을 한단계씩 줄여가며 before와 next를 더해가는겁니다. 


한 타임이 지나면

before는 next가 되며

next는 before + next가 됩니다.


그렇게 반복되며 꼬리재귀함수를 돌다가 n값이 0 이라면 현재 값(before)를 반환합니다.


꼬리 재귀 함수에 관해선 다른 포스팅에서 자세히 다루도록 하겠습니다.



감사합니다.



Posted by 시리시안