[Algorithms] Fibonacci Sequence | 피보나치 수열

Fibonacci Sequence

피보나치 수열

\(f(n) = f(n-1) + f(n-2)\\
f(1) = f(2) = 1\)

- 즉, 피보나치 수는 \(n-1\)의 피보나치 수와 \(n-2\)의 피보나치 수를 포함하고 있는 수 이다. 
- 즉, 피보나치 수열에서는 다음 항을 구하려면, 이전 항의 값을 알아야 하기 때문에
  피보나치 수열은 Optimal Substructure를 가졌다 할 수 있으며,
  이는 Dynamic Programming 기법이 적용 가능함을 의미한다.

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

---

Implementation (구현)

1. Stupid Recursion (\(\Omega(2^{n \over 2})\))

fib(n)
{
    if (n == 1 || n == 2)
        return 1;
    else
        return (fib(n-1) + fib(n-2));
}

- 위 알고리즘에서 fib(7)의 값을 구하는 경우, fib(5)는 2번, fib(4)는 3번, fib(3)은 5번, fib(2)는 8번이 호출된다.
- 즉, 한 번 구한 값을 계속해서 구하게 하는 비효율을 야기한다.
  그러므로, 한 번 구해놓은 값을 저장해놓음으로써 비효율을 개선할 수 있다.

* 흥미로운 점은, 이러한 중복 호출 회출 자체도 피보나치 수열을 이룬다는 것이다.

fib(n)	fib(2)의 호출 횟수
fib(3)	1
fib(4)	2
fib(5)	3
fib(6)	5
fib(7)	8
fib(8)	13
fib(9)	21
fib(10)	34

---

2. Dynamic Programming with Loop (\(\Theta(n)\))

fib(n)
{
    f[1] = f[2] = 1;
    
    for(int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
 
    return f[n];
}

- Bottom-Up Approach

---

3. Dynamic Programming with Recursion (\(\Theta(n)\))

fib(n)
{
    if(f[n] != 0)  // 아직 계산되지 않은 항은 모두 0으로 초기화되어 있다 가정한다.
        return f[n];
    else {
    	if (n == 1 || n == 2)
            f[n] = 1;
        else
            f[n] = fib(n-1) + fib(n-2);
            
        return f[n];
    }
}

- Top-Down Approach (by Memoization)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)