fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.

예시
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n
number 타입의 n (n은 0 이상의 정수)

출력

number 타입을 리턴해야합니다.

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

let output = fibonacci(0);
console.log(output); // --> 0

output = fibonacci(1);
console.log(output); // --> 1

output = fibonacci(5);
console.log(output); // --> 5

output = fibonacci(9);
console.log(output); // --> 34

Advanced

피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

내 답안

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  let memo = { }
  function fibo(n){
    memo = memo || { };
    if(memo[n]) return memo[n];
    if(n < 2){
      return n;
    }
    return memo[n] = fibo(n-2)+ fibo(n-1);
  }
  return fibo(n, memo);
}

당시 내 생각

나는 처음 fibonacci가 재귀가 아니어도 된다는 소리가, 재귀 없이도 풀 수 있다는 말로 들었다. 그래서, output case가 몇개 없나라는 생각을 했다. 이후에 그럼 함수를 하나 만들어서 재귀를 돌리면 되지라는 생각을 하게되서 fibo라는 함수를 만들었다. memo는 최외곽 스코프인 fibonacci scope에서 유지되기를 바래서 재귀 부르기 전에 선언해서 memo를 객체로 썼다. 레퍼런스를 보니 꼭 객체가 아니어도 index로 충분히 대응이 된다는 사실을 보고 쫌 열받긴 했다.

memo는 최외곽에 선언해두어서, 인자로 보내지 않아도 되는데 약간 늦게 풀기시작해서 나사가 하나쯤 풀려있었나보다. memo가 리턴에도 있다. 이런 것들은 디테일하지 못하고 프로답지 못하다.(프로도 아니다.)

아무튼 이후에 객체[키] 값의 존재유무로 memo[n]을 리턴하는 식으로 기존값에 대응하고 n < 2 작은 경우에는 자기 자신을 넣어줘서 memo에 쌓이게 했다. 결과적으로 말하면 fibo(0) = 0, fibo(1) = 1 이 만들어진다. return에서는 fibo(n-2)와 fibo(n-1)를 memo에 적음과 동시에 리턴시켜서 바로 memo[n]에 저장해두었다.

문제는 너무 멍청하게도, memo가 변동된다는 사실을 잊고 memo = { };로 선언해두었다. 그래서 계속적으로 memo가 비워지게 되었고 답이 나오질 않았다. 그 문제에서 바로 손코딩에 접속했고, memo가 빈다는 사실을 알고 수정시켰다.

알게된 점

다른건 다 괜찮은 접근이었는데, memo를 선언해두고 계속 잊어버렸다. 당연히 외곽에 있어서 신경 안써도 된다고 생각을 하고 계속해서 문제풀이를 이어나갔는데 결국 call할수록 초기화되는 멍청한 루틴에 빠져서 문제를 풀 수 없는 상황이 왔다. memoization 풀이를 할때에는 메모가 제대로 유지되어야하는건데 제일 중요한 부분이 나사가 풀려있었다. 앞으로 재귀나 memo 기법을 사용해야할때, storage가 되는 변수는 변화하지 않도록 유의해서 풀이를 접근해야겠다는 생각을 했다.