[JavaScript] 피보나치 수(Fibonacci numbers) 만들기 - 메모이제이션

피보나치 수란?

피보나치 수는 0번째 항이 0, 1번째 항이 1, 2번째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수입니다.

 

점화식

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

 

피보나치 구현

피보나치는 같은 형태의 작업을 반복하기 때문에, 재귀함수를 이용해 구현하는 경우가 많습니다.

 

재귀함수를 이용한 피보나치 구현1

function fibonacci(num) {

  if (num === 0) return 0

  if (num === 1) return 1;

  return fibonacci(num-1)+fibonacci(num-2);

}

 

소스코드를 보면 num이 0일때는 0, num이 1일때는 1을 반환합니다.

즉 num이 1이하일 경우, num을 반환한다고 볼 수 있습니다.

 

재귀함수를 이용한 피보나치 구현2

function factorial(num) {

  if (num <= 1) return num;

  return fibonacci(num-1)+fibonacci(num-2);

}

 

메모이제이션

동일한 계산을 반복해야 하는 경우, 이전에 계산한 결과를 메모리에 저장해 동일한 계산의 반복을 방지하는 기술입니다.

재귀함수의 경우 동일한 계산이 많이 반복되어 메모이제이션을 사용하면 많은 계산을 줄일 수 있습니다.

 

메모이제이션을 사용한 피보나치 구현

function fibonacci(n) {

  let memo = [0, 1] // 이전 계산이 저장된 배열, 0번째와 1번째의 값은 0과 1

  let calFibo = (num) =>{

    if(memo[num] !== undefined) return memo[num] // 이전에 계산한 값이 있다면, 바로 반환

    memo[num] = calFibo(num-1) + calFibo(num-2) // 계산한 값이 없다면, 계산 후 memo에 저장

    return memo[num];

  }

  return calFibo(n);

}