28. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘

1. 개요

 피보나치 수열의 알고리즘은 정말 쉬움.

 크게 3가지 방식 존재. (1) 재귀(recursion), (2) 동적 프로그래밍(Dynamic Programming), (3) 반복(For문)

 피보나치 수열의 BigO()는 방식에 따라 다름.

 (1) 재귀: BigO(2^n), (2) 동적: BigO(n^2), (3) 반복: BigO(n).

 안정성 문제로 가장 좋은 방법은 바로 반복이다. 

 재귀나 동적은 연속 함수 호출로 인한 Stack Overflow 문제가 발생 가능성 높음. 

 데이터 크기가 급속도로 커져서 정수형(int)로는 값을 받아들이기 어려움.

 피보나치의 원래 이름은 '레오나르도' 임. 피보나치는 별명.

 피보나치의 뜻은 '보나치의 아들'이라는 뜻으로 18세기 프랑스 수학자 '기욤 리브리'가 만들었다는 설이 존재.

2. 문제

 피보나치 수열의 원본

 [ '계산 책'의 세 번째 장에서는 피보나치가 처음 내놓은 것으로 보이는 문제가 실려있다. ]

 - 어떤 사람이 모든 면이 벽으로 둘러싸인 장소 안에 토끼 한 쌍을 놓아둔다. 만약 매달 각 쌍의 토끼가

   새로운 쌍을 낳고, 이 새로 태어난 쌍은 다음 달부터 번식이 가능하다. 그렇다면 일 년 후에는 토끼가

   몇 쌍이 될 것인가?

 이 문제에서 흥미로운 다음의 수열이 등장한다. 이것이 피보나치의 수열이다.

 - 1 2 3 5 8 13 21 34 55 ...

 피보나치 수열을 재귀, 동적, 반복으로 모두 구하시오.

3. 출력

3-1) 재귀 알고리즘

3-2) 동적 알고리즘

3-3) 반복 알고리즘

3-4) 각 알고리즘 비교 출력

      (1) 크기 40일 때

       (2) 크기 50일 때(리커젼 방식은 너무 오래 걸려서 제외) 

4. 정리

 피보나치 수열을 푸는 여러가지 방식에 대한 문제는 지금껏 기업 필기 테스트나 면접을 보는 동안 약 3번을 만났다.

 문제에서 요구하는 것은 피보나치 수열을 푸는 가장 기본적인 방법인 리커젼 방식의 위험을 알고 반복적인 방법으로

 고칠 수 있는 지 요구하였다. 그러므로 피보나치 수열에는 이 3가지 방식에 대한 방법이 존재한다는 것을 확실히 알자.

 그리고 피보나치 수열이나 팩토리얼 문제나 똑같다.

 기억해야 할 것.

 (1) 재귀적 방식, 동적 프로그래밍 방식, 반복적인 방식 존재.

 (2) 동적과 반복은 기존 계산된 값을 저장할 테이블을 선언해야함.