나무 숲

피보나치 수열 Fibonacci Numbers / Fibonacci Sequence 본문

Career/알고리즘 · 자료구조

피보나치 수열 Fibonacci Numbers / Fibonacci Sequence

wood.forest 2017. 4. 3. 22:54

피보나치 수

Fibonacci Numbers


수학에서 아래의 점화식으로 정의되는 수열이다.

피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. 


* 피보나치 수열은 서로 인접한 항끼리 서로 소이다. 이것은 귀납법으로 간단히 증명할 수 있다.

* 피보나치 수열의 인접한 두항의 비(fn +1 / fn)는 황금비(1:1.6180339887...)에 수렴하는 성질이 있다.








피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다. 

유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다.


n 번째 달의 토끼 수는 : 


첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.

두 달 이상이 된 토끼는 번식 가능하다.

번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.

토끼는 죽지 않는다.

따라서 첫 달에는 새로 태어난 토끼 한 쌍이 있고, 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 이때 n번째 달에 a 쌍의 토끼가 있었고, 다음 n+1 번째 달에는 새로 태어난 토끼를 포함해 b 쌍이 있었다고 하자. 그러면 그다음 n+2 번째 달에는 a+b 쌍의 토끼가 있게 된다. 이는 n번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전달인 n+1번째에 막 태어난 토끼는 아직 새끼를 낳을수 없기 때문이다.




n = 0, 1,...에 해당하는 피보나치 수열은

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...







코드






재귀

실제로 재귀는 프로그램을 복잡하게 하고 단순 반복문보다 느리다고 합니다..





메모이제이션

동적 계획법의 핵심으로, 실행 속도를 획기적으로 단축시켜 줍니다.


위 그림을 보시면 fib(4)를 계산하는 데에 f(1)이 세 번, f(0)이 두 번 반복되어 사용되는 것을 알 수 있습니다.

allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;

fib(n) {
   if memo[n] is zero:
       memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}

메모이제이션을 통한 피보나치 수 저장은 위와 같습니다.

메모를 할 배열을 할당하고 모든 요소를 0으로 초기화하는데, f(1)과 f(2)의 값은 미리 1로 셋팅해놓습니다.

함수 fib(n)은, 메모 배열[n]에 값이 없을 때엔 계산하여 값을 넣을 것이고 최종적으로는 메모배열[n]의 값을 불러올 것입니다.


배열 크기 50의 코드는 아래와 같습니다.


-

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

https://www.thinglink.com/scene/656850248605368322

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

728x90
반응형
Comments