[TIL] fibonacci

• 문제 : 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
• 주의사항 : 재귀함수를 이용해 구현

let fibonacci = function (n) {
  const memo = [0, 1]; 
  const last = (n) => {
  
    if (memo[n] !== undefined)
     return memo[n]; //풀었던 문제는 그 결과를 그대로 리턴
    
    memo[n] = last(n - 1) + last(n - 2);
    return memo[n]; //새로 풀어야 되는 문제
  }
  return last(n);
}

• 풀고난 후 : 하향식 구조라고 생각했지만
  재귀를 이용해서 상향식으로 나가는 상향식 구조로 추측된다.
  Top-Down 방식에 해당된다.
  -한 번 계산한 결과를 메모리 공간에 메모해서 값을 기록하는데, 캐싱이라고 한다.
  다이나믹 프로그래밍의 형태는 bottom-up으로 for문으로 작은 수 부터 계산되는방식인데
  결과를 저장함으로써 이 문제는 메모이제이션을 사용하여 탑다운 방식을 구형가능하게 한것으로 보인다.
  피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재한다.
  중간에 보여지는 memo는 이미 해결한 문제의 정답을 따로 기록해두고, 다시 해결하지 않는 기법이다.

• 아쉬운점 : 탑타운 방식과 바텀업 방식에 대해서 다음 블로깅을 하고자 한다.