프로그래머스 - 피보나치_수열

피보나치

1. 이해

   • 피보나치 수열을 구하자
   • 0 1 1 2 3 5 => 5를 구하려면 3 + 2 / 3을 구하려면 2 + 1

2. 계획

   • 재귀 함수로 구하자
   • 메모라이징 패턴으로 효율성을 올리자

3. 코드

   const solution = n => {
       const arr = [0, 1];
       for(let i = 1; i < n; n++){
           arr.push((arr[i]+arr[i-1])%1234567)
       }
       return arr[n]
   }
   //방법1(반복)
   const fiboArr = n => {
       const arr = [0, 1]
       for(let i = 1; i < n; i++){
           arr.push(arr[i] + arr[i - 1])
       }
       return arr[n]
   }
   //방법2(재귀)
   const basic = (n) => {
       if(n <= 1){
           return n
       }else{
           return basic(n-1) + basic(n-2)
       }
   }
   //방법3(재귀 + 캐쉬)
   const fibonacci = n => {
       const cache = [];
       const fibo = (n) => {
         if (typeof(cache[n]) === 'number') {
             return cache[n];
         }else if(n <= 1){
             return cache[n] = n
         }else {
             return cache[n] = fibo(n - 1) + fibo(n - 2);
         }
       };
       return fibo(n);
     };

4. 반성

   • 문제 이해(제한조건)를 하자(나머지를 구하는것이다)
   • 배열은 되는데 재귀함수는 되지 않는다.