← 13주차 · 재귀와 분할 정복
쉬움재귀메모이제이션

재귀 피보나치와 메모이제이션

정수 n이 주어져요. n번째 피보나치 수를 반환해요. 피보나치 수는 fib(0) = 0, fib(1) = 1이고, 그 뒤로는 fib(k) = fib(k-1) + fib(k-2)예요.

그냥 재귀로 짜면 같은 값을 몇 번이고 다시 계산해서 아주 느려요. 한 번 구한 값을 저장해 두고 다시 쓰면(메모이제이션) O(n)에 끝나요. 이 저장 습관이 19주차 DP로 이어져요.

예시

예시 1
입력
n = 10
출력
55
설명
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 에서 10번째가 55예요.
예시 2
입력
n = 0
출력
0

제한 사항

  • 0 ≤ n ≤ 70
memo 맵을 두고, fib(k)를 구하기 전에 이미 저장돼 있으면 그대로 꺼내 써요. 없으면 fib(k-1) + fib(k-2)로 구해서 저장한 뒤 반환해요. 기저 조건은 k <= 1일 때 k 그대로예요.
javascript
function fibonacciMemo(n) {
  const memo = new Map();
  function go(k) {
    if (k <= 1) return k;
    if (memo.has(k)) return memo.get(k);
    const value = go(k - 1) + go(k - 2);
    memo.set(k, value);
    return value;
  }
  return go(n);
}
이전 문제예산 배정
다음 문제거듭제곱 빠르게
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.