피보나치 수와 C# LINQ

피보나치 수는 0과 1로 시작하고 그 다음 항들은 전전 항과 전 항의 합으로 정의되는 수열로서, 다음과 같이 증가하는 형태를 띄고 있다:

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

과학 분야에서는 이런저런 쓰임새가 있다고 하는데 컴퓨터 분야에서는 주로 재귀 호출(함수가 자신을 호출하는 것)의 예로 널리 사용되며, 그 다음으로는 C/C++ 프로그래머를 애먹이는(?) 문제를 출제하는 데 사용된다. 나머지 쓸모는 딱히 없는 듯...?

지난번 입사시험 퀴즈에 이어 사이냅소프트 블로그를 더 살펴 봤더니 예전에 피보나치 수를 이용한 퀴즈가 출제된 적이 있었다. 12345678999(123억...)과 99987654321(999억...) 사이의 피보나치 수를 모두 더하면 얼마인가 하는 문제다. 여기서는 C/C++로 푼 것과 C#으로 LINQ를 이용해서 푼 것을 비교해 보기로 하겠다. 일단은 일반적인 해법부터 잠깐.

재귀를 이용한 방법

프로그래밍 언어에 상관없이 피보나치 수를 구하는 가장 쉬운 방법은 재귀를 이용하는 것이다. 예를 들어 C/C++로 짠다면

int64_t Fibonacci(int n)

{

    if (n <= 1)

        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);

}

C#으로 짠다면:

public static long Fibonacci(int n)

{

    if (n <= 1)

        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);

}

람다식을 이용한 C# 코드도 모양만 약간 다를 뿐 알고리듬은 동일하다:

public static long Fibonacci(int n)

{

    Func<int, long> fib = null;

    fib = x => x > 1 ? fib(x - 1) + fib(x - 2) : x;

    return fib(n);

}

기타 약간씩 변형한 방법도 있지만 기본 원리는 모두 동일하다.

위의 재귀적 방법의 가장 큰 단점은 항이 커질 수록 속도가 급격하게 떨어진다는 데 있다(시간이 지수적으로 증가함). 예를 들어 Fibonacci(45)를 구하려면 Fibonacci()가 36억회(오타 아님) 이상 호출된다.

재귀를 이용하지 않는 방법

이것은 반복(iteration)이라고 해서 재귀 대신 루프를 이용하는 방식이다.

int64_t Fibonacci(int n)

{

    if (n <= 1)

        return n;

    int64_t prev2 = 0, prev = 1;

    int64_t fib;

    for (int i = 2; i <= n; i++)

    {

        fib = prev2 + prev;

        prev2 = prev;

        prev = fib;

    }

    return fib;

}

이 방법의 장점은 시간이 n의 크기에 비례한다는 점이다(복잡도 O(n)). 따라서 재귀적 방법에서 나타나는 급격한 성능 저하가 발생하지 않는다.

사이냅 퀴즈 풀이

[업데이트] C로는 아래처럼 루프를 돌려서 답을 구할 수 있다. 다만 중간값을 저장할 필요가 있는 문제가 출제된다면 표준 라이브러리에 컬렉션이 없는 C로서는 상당한 닭질이 요구되므로 C++로 작성하는 편이 낫다.

int64_t sum = 0;

 

for (int i = 0; ; i++)

{

    int64_t fib = Fibonacci(i);

    if (fib >= 99987654321LL)

        break;

    if (fib > 12345678999LL)

        sum += fib;

}

C++로는 STL을 이용하면 중간값을 저장하기도 쉽고 결과값을 얻는 것도 쉽다:

vector<int64_t> v;

 

for (int i = 0; ; i++)

{

    int64_t fib = Fibonacci(i);

    if (fib >= 99987654321LL)

        break;

    if (fib > 12345678999LL)

        v.push_back(fib);

}

 

int64_t sum = accumulate(v.begin(), v.end(), 0LL);

여기 사용한 accumulate()는 이터레이터를 돌면서 누적합을 구해주는 함수로서, <numeric>에 정의되어 있다. 마지막 파라미터의 0LL은 덧셈에 대한 항등원으로 지정한 것이다.

LINQ로 만든 피보나치 수열 API

LINQ를 이용한 C# 구현은 수열을 생성한다는 점에서 특정 항의 피보나치 수를 구하는 기존 구현들과 다르고, 원리상으로는 위의 반복 알고리듬과 동일하다:

public static IEnumerable<long> Fibonacci()

{

    yield return 0;

    yield return 1;

 

    long prev2 = 0, prev = 1;

    long fib;

    while (true)

    {

        fib = prev2 + prev;

        if (fib < prev)

        {

            yield break;

        }

        yield return fib;

        prev2 = prev;

        prev = fib;

    }

}

한가지 주의해야 할 점은 피보나치 수가 64비트 경계를 뛰어넘는 순간 수열 생성을 종료해야 한다는 것이다(yield break 문을 쓰거나 제어가 메쏘드 끝에 도달하게 만들거나 해서). 이 조건이 없으면 무한 루프가 종료되지 않으며 나중에 수열이 엉망이 되고 만다.

아울러 특정 항을 구하는 메쏘드도 쉽게 만들 수 있다:

public static long Fibonacci(int n)

{

    return Fibonacci().ElementAt(n);

}

LINQ로 푼 사이냅 퀴즈

[업데이트] C/C++로는 루프와 이터레이터를 이용해서 썩 깔끔하지 못하게 풀었던 문제가 LINQ로는 쉽고 직관적으로 해결 가능하다. 아래처럼 데이터베이스 쿼리를 하듯이 짜면 된다:

var sum = Fibonacci().Where(fib => 12345678999 < fib && fib < 99987654321).Sum();

여기서 생각해볼 문제: 64비트 정수 범위 내에서 구할 수 있는 가장 큰 피보나치 수는 몇번째 항의 얼마일까? 역시 LINQ를 이용하면 아주 쉽게 풀 수 있다.

피보나치 수의 미스테리

여기저기 보면 꽃잎의 수가 대부분 피보나치 수를 따른다고 되어 있다(어디서는 90% 이상이 그렇다고). 그런데 아주 오래전 들판에 놀러 나가서 여러가지 들꽃을 꺾어 꽃잎의 수를 세어본 적이 있었는데, 피보나치 수와 맞는 꽃이 한 개도 없는 것이 아닌가. 지금도 보면 집 마당에 모란 꽃이 피어 있는데 이건 꽃잎 수가 14장에서 18장까지 다양하다. 밑에 피어 있는 비둘기풀(?)의 꽃잎은 4장이고... 여러분도 한번 세어보시기 바란다.