[알고리즘] 피보나치 수열 - dp를 알기위한 사전단계

피보나치 수열의 유래?  피보나치 수열은 규칙을 발견한 수학자 레오나르도 피보나치의 이름을 따 부르게 되었다.

 

레오나르도 피보나치는 이탈리아 수학자로 이집트, 그리스, 시칠리아 등의 나라를 여행하며 아라비아에서 발전된 수학을 두루 섭렵하였다고한다. 그 많은 업적 중 피보나치수열은 12세기말 이탈리아에서 처음 제안한 것으로 "한 쌍의 토끼가 계속 새끼를 낳으면 몇 마리로 불어 날까?를 연구하다 새로운 수의 체계를 발견하였다고 한다.

 

한쌍의 토끼는 매일 암수 한쌍의 새끼를 낳으며 새로 태어난 토끼도 태어난지 두달 후 부턴 매달 한쌍씩 암수 새끼를 낳는다고 한다. 그러면 

농장주는 1년이 지난후 모두 몇쌍의 토끼를 갖게 될까?

 

 

 

 

그 결과 피보나치는 매달 관찰되는 토끼의 양이 특정한 규칙을 따르고 있음을 발견했다.

12월 말에 144쌍의 토끼를 예상하였다.

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

 

 

이렇게 규칙이있는 것을 알수있었다.

 

동일한원리에서 식물의 줄기도 나오긴한다. 식물이 두갈래로 갈라지기 위해서는 줄기의 굵기가 어느 정도 이상이여야 한다.

그리고 필요한 굵기 이상이 된 이후에는 정기적으로 가지치기를 할 수 있다. 그원리가 토끼의 번식과 완전히 동일하다.

꽃잎의 모태가 되는 입자도 어느정도 성장하고 나서 작은 새끼 입자 하나를 낳고 그것이 다시 새로운 입자를 낳기위해서는 특정한 시간이 필요하다고 가정한다면 꽃잎이나 씨앗의 갯수에서도 피보나치 수열이 나타나는 것을 알수있다.

솔방울의 한쪽방향 8개 나선, 다른방향 13개의 나선

 

피아노 건반의 한 옥타브 사이에는 5개의 까만 건반, 8개의 하얀 건반, 모두 13개의 건반이 있다. 우연인가?

 

그 토끼 현상을 자바스크립트코드로 풀면 이렇게 나올거같다.

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

클로저를 활용한 풀이

 

const fibonacci = (() => {
  const memo = {};
  function f(n) {
    if (n in memo) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;
    memo[n] = f(n - 1) + f(n - 2);
    return memo[n];
  }
  return f;
})();