Jun 개발노트

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

January 13, 2020

피보나치

  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. 반성

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

Written by Junho You 배운것을 기록하자