Fibonacci Sequence   피보나치 수열

1. 피보나치 수열

  ㅇ 연속한 두 수의 합이 그 다음 수가 되는 수열
     -  {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... } 

  ㅇ 표현식 : 재귀적으로 표현 가능              ☞ 점화식 참조
     -  Fn = Fn-1 + Fn-2  또는  Fn+1 = Fn + Fn-1
        . 단, F0 = 0, F1 = 1


2. 피보나치 수열의 특징

  ㅇ 각 항은 바로 앞의 두 항의 합으로 결정됨
  ㅇ 항의 크기가 증가할수록 급격히 커짐 (지수적 증가)
     - 예로써,
        
[# F_n = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right) ^n #]
        . {#\frac{1+\sqrt{5}}{2} \approx 1.618#}은 황금비
        . 피보나치 수는 약 1.618n의 속도로 커짐
        . (거의 2n에 가까운 지수적 증가)


3. 피보나치 수열을 구하는 알고리즘 例)

  ㅇ 재귀 호출 방식 (비효율적 방식)
     - 재귀의 수학적 정의를 그대로 구현하지만, 동일한 계산을 여러 번 반복하므로 매우 비효율적
       
function fib(n)
    if (n < 1) return 0 
    else if (n == 1) return 1 
    return fib(n-1) + fib(n-2)
        . 동일한 인수로 fib(n)을 여러 번 호출 (중복 계산 발생)
           .. 만일, fib(5)를 구하려면, fib(3),fib(4) 모두를 구해야 하고,
           .. 그 안에서 다시 fib(2)를 반복 호출함 → 지수적 증가
        . 시간 복잡도 : O(2n)

  ㅇ 반복문 + 동적 계획법 (개선된 방식)
     - 이미 계산한 값을 DP 배열에 저장하여 재사용하는 방식
       
function fib(n)
    create array dp[0..n]
    dp[0] = 0
    dp[1] = 1
    for i = 2 to n
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
        . (반복문) 재귀 호출이 아닌 반복문을 사용하여 반복처리
        . (동적계획법)
           .. 작은 문제(dp[0], dp[1])부터 시작
           .. 이전 두 값을 더해 새로운 값을 생성
           .. 이미 구한 값은 DP 배열에 저장하여 재사용
        . 시간 복잡도: O(n), 공간 복잡도: O(n)