피보나치 수열 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

피보나치 수열(Fibonacci Sequence)의 정의

현재항의 값이 이전 2개 항의 합으로 계산되는 수열.

컴퓨터 과학에서는 주로 0번째 항이 0인 피보나치 수열을 사용한다. ( 0, 1, 1, 2, ... )

아래는 200번째 인덱스까지의 피보나치 수열 테이블이다.

fibonacci_seq_upto200.txt

출처 : OEIS_A000045

피보나치 수열 알고리즘 개요

N번째 피보나치수를 알고 싶다면, 정의에 따라 N-1, N-2번째 피보나치 수를 알고 있어야 한다.

정리하자면, 얼마나 효율적으로 N-1, N-2를 가져오느냐가 전체 성능을 좌우한다.

아래는 피보나치 수열을 만들때 사용하는 방법들이다.

Function Information

fibo_recursion(n)	재귀를 이용하여 n번째 피보나치 수를 구한다.
fibo_recursion_memoized(n)	메모이제이션이 적용된 재귀를 이용하여 n번째 피보나치 수를 구한다.
fibo_iterative(n)	순회를 이용하여 n번째 피보나치 수를 구한다.
fibo_iterative_queue(n)	원형 큐를 이용한 순회를 이용하여 n번째 피보나치 수를 구한다.
fibo_matrix(n)	행렬을 이용하여 n번째 피보나치 수를 구한다.
fibo_matrix_fast(n)	빠른 곱셈 알고리즘이 적용된 행렬을 이용하여 n번째 피보나치 수를 구한다.
pisano(mod)	mod로 나눴을 때의 피사노 주기를 구한다.

RunningTime Statistics (1,000,000회 평균값)

	10	30	60	90	Time	Memory
fibo_recursion()	4.9 μs	50 ms	X	X	2^n	1
fibo_recursion_memoized()	0.5 μs	1.7 μs	3.1 μs	4.7 μs	nearly n	n
fibo_iterative()	0.1 μs	0.15 μs	0.27 μs	0.34 μs	n	n
fibo_iterative_queue()	0.16 μs	0.37 μs	0.75 μs	0.96 μs	n	1
fibo_matrix()	0.30 μs	1.1 μs	2.45 μs	3.77 μs	n	1
fibo_matrix_fast()	0.31 μs	0.39 μs	0.43 μs	0.44 μs	log n	1

* 각 테스트케이스마다 캐싱된 값을 초기화하고 실행하였음.

1. 재귀

<핵심>

    1. 가장 직관적으로 점화식을 사용한다.

    2. 성능은 보장할 수 없다. O(2^n)

각 단계의 Fib 함수가 2개씩 나눠지며 총 2^(5-1)개의 함수가 호출되었다.

같은 단계의 함수가 다시 호출했을 때, 중복된 계산이 발생하여 성능이 저하된다.

위의 트리에서 모든 Fib(2)가 매번 Fib(1), Fib(0)을 호출한것에 주목하자.

자신의 결과 값을 캐싱하고 있었다면(메모이제이션), 아랫단계의 함수를 호출할 필요가 없다.

2. 메모이제이션이 적용된 재귀

<핵심>

    1. 메모이제이션을 적용하여 중복된 계산이 발생하지 않도록 한다.

    2. 시간복잡도는 순회와 재귀 사이에 있다.  (시간복잡도 nearly n)

위는 메모이제이션이 적용되었을 때의 Fib(6)의 호출트리이다.

한번 실행되었던 단계가 다시 호출되었을 때, 단순히 캐싱값만 내어준다.

3. 순회

<핵심>

    1.  보통 순회를 이용하면, 재귀보다 직관적이지 못하다.

    2.  간단한 알고리즘에서는 재귀, 순회 둘 다 직관적이다.

    3.  왠만한 경우에서 재귀보다 훨씬 빠르게 동작한다.  (시간복잡도 n)

4. 원형큐가 적용된 순회

<핵심>

    1.  일반적인 순회는 메모리를 n 만큼 잡아먹는다, 원형큐를 사용하여 메모리 복잡도를 1로 줄이자.

    2.  원형큐의 인덱스를 계산하는데 오버헤드가 있다.

    3.  중간과정이 필요한 경우에는 적절하지 않다. (어차피 n만큼 캐싱해야 되기 때문.)

5. 행렬

<핵심>

    1.  행렬의 곱을 이용한다.

<피보나치 행렬의 증명>

출처 : 스택 오버플로우

6. 빠른 곱셈이 적용된 행렬 (Bottom-Up)

<핵심>

    1.  A^2n = A^n * A^n 임을 이용하여 절반으로 쪼갠다.  (빠른 곱셈 알고리즘)

    2.  TopDown 혹은 BottomUp으로 구현할 수 있다.

        TD : 재귀처럼 위에서 아래로 계산한다. (2씩 나눈다.) 32 -> 16 -> 8 -> 4 -> 2 -> 1 

        BU : 순회처럼 아래에서 위로 계산한다. (2씩 곱한다.) 1 -> 2 -> 4 -> 8 -> 16 -> 32

    3.  각 단계를 절반으로 쪼개므로 시간복잡도는 log n 이다.

피사노 주기

<핵심>

    1.  피보나치 수열을 mod n 했을 때, 반복되는 구간이 형성된다.

    2.  매 반복되는 구간의 첫 부분은 항상 {0, 1, 1} 이다.

    3.  주기가 찾아질 때 까지 메모리를 끝없이 잡아먹으므로, 원형큐 피보나치를 이용한다.

피보나치 린덴마이어 시스템 (Lindenmayer-System, L-System)

다음 규칙을 따르는 린덴마이어 시스템을 정의하자.

variables : A B

constants : none

start : none

rules : (none → A), (A → B), (B → AB)

위의 L-시스템을 따르는 시퀀스는 아래와 같고,

n = 0 : none

n = 1 : A

n = 2 : B

n = 3 : AB

n = 4 : BAB

n = 5 : ABBAB

n = 6 : BABABBAB

n = 7 : ABBABBABABBAB

각 시퀀스의 문자열의 길이는 피보나치 수열을 따른다.

    0 1 1 2 3 5 8 13 ...

기하에서의 피보나치

아래와 비슷한 기하의 규칙은 피보나치 수열와 관련이 있다.

알고리즘 문제에서 숨어있는 규칙으로 많이 나온다.

<피보나치 블럭>

<피보나치 나선>

<피보나치 + 파스칼 삼각형>

피보나치 수열은 파스칼 삼각형에서의 우상 대각선의 합이다.

파스칼 삼각형으로 표현할 수 있다면, 이항계수로도 표현될 수 있다.

출처 : 스택 오버플로우