[Javascript] 피보나치 수열 - 알고리즘

피보나치 수열이란?

---

수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 
수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.
출처 - 위키백과

피보나치 수열 구현

---

피보나치 수열을 구현하는 방식은 다양하지만 여기서는 재귀 함수를 이용한 방식과 재귀 함수의 문제점을 개선한 메모이제이션(Memoization) 기법을 사용할 예정이다.

구현해야 할 것
1. 인자에 n을 넣었을 때 피보나치 수열의 n 번째 값을 return [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... ]
2. n = 1일때와 n = 2일 때는 1을 return

1. 재귀 함수를 이용해 피보나치 수열 구현

먼저 재귀 함수를 이용해 피보나치 수열을 구현해 보자.

피보나치 수열의 n번째 항의 값은 (n-1) 번째 항과 (n-2) 번째 항의 합과 같다.

그리고 n=1일때와 n=2일 때는 값이 이다.

function fibo(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fibo(n - 1) + fibo(n - 2);
}

처음에는 위와 같이 코드를 작성했다.

n=1일 때와 n=2일 때는 조건문을 사용해 1을 return 해주고 그렇지 않다면 (n-1)항과 (n-2) 번째 항을 더한 값을 return 하도록 작성했다.

하지만 이 코드에는 문제가 있다.

바로 같은 계산을 또 한다는 것이다.

console.log(fibo(6));

• fibo(1) => 1
• fibo(2) => 1
• fibo(3) => fibo(2) + fibo(1)
• fibo(4) => fibo(3) + fibo(2) => fibo(2) + fibo(1) + fibo(2)
• fibo(5) => fibo(4) + fibo(3) => fibo(3) + fibo(2) + fibo(2) + fibo(1) => fibo(2) + fibo(1) + fibo(2) + fibo(2) + fibo(1)
• fibo(6) => fibo(5) + fibo(4) => fibo(4) + fibo(3) + fibo(3) + fibo(2) => fibo(3) + fibo(2) + fibo(2) + fibo(1) + fibo(2) + fibo(1) + fibo(2) => fibo(2) + fibo(1) + fibo(2) + fibo(2) + fibo(1) + fibo(2) + fibo(1) + fibo(2)

보이는 것과 같이 같은 계산이 반복되고 n의 값이 클 수록 반복되는 부분이 많아지고 있다.

그렇다면 이미 저장한 값은 저장해 놓으면 어떨까?

2. 메모이제이션 기법을 사용해 피보나치 수열 구현

메모이제이션(Memoization) 기법이란?
- 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.
- 다이나믹 프로그래밍을 구현하는 방법 중 한 종류

메모이제이션 기법을 사용해 반복되는 값은 저장해 놓았다가 그 값이 필요할 때 사용하면 조금 더 속도가 빨라질 것 같다.

let memo = {};

function fibo(n) {
  let result;

  if (n in memo) {
    result = memo[n];
  } else {
    if (n == 1 || n == 2) {
      result = 1;
    } else {
      result = fibo(n - 1) + fibo(n - 2);
    }
    memo[n] = result;
  }
  return result;
}

재귀 함수 코드를 다음과 같이 수정해보았다.

일단 값을 저장할 memo라는 객체를 전역으로 선언하고 함수를 선언했다.

함수를 살펴보면 이전 코드와 유사하다.

다른 점이라면 만약 객체 memo에  n이라는 속성명이 존재한다면 result에 memo 객체의 n이라는 속성명을 가진 속성 값을 대입해 준다는 점이다.

만약 속성명이 존재하지 않는다면 재귀함수 코드를 실행한 다음 결과 값을 result에 대입해준 후 memo객체의 n이라는 속성명으로 result 값을 대입해준다.

console.log(fibo(6));
console.log(memo);

메모이제이션 실행 결과

두 방식의 실행 속도 차이

---

두 방식의 속도가 어느정도 차이나는 지 한번 확인해 보자

n값이 클 수록 차이가 많이 난다.

console.time("피보나치 - 재귀함수");
function fibo(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  return fibo(n - 1) + fibo(n - 2);
}

fibo(50);
console.timeEnd("피보나치 - 재귀함수");

재귀함수로 피보나치 수열의 50번째 값을 구한 시간

console.time("피보나치 - 메모이제이션");
let memo = {};

function fibo(n) {
  let result;

  if (n in memo) {
    result = memo[n];
  } else {
    if (n == 1 || n == 2) {
      result = 1;
    } else {
      result = fibo(n - 1) + fibo(n - 2);
    }
    memo[n] = result;
  }
  return result;
}

fibo(50);
console.timeEnd("피보나치 - 메모이제이션");

엄청난 속도의 차이를 볼 수 있다!

마무리

---

 

어떤 코드가 더 좋은 코드인가는 상황에 따라 다를 수 있다.

n 값이 크지 않다면 두 코드의 속도 차이는 거의 없었다. (오히려 재귀 함수 코드가 더 빠를 때도 있었다.)

n 값이 작은 상황에서는 읽기 쉽고 이해하기 쉬운 재귀함수를 이용한 코드가 더 좋다고 생각한다.

하지만 n 값이 커지게 되면 속도 차이가 매우 벌어지는 결과를 볼 수 있듯이 n 값이 큰 상황에서는 메모이제이션 기법을 사용한 코드가 더 좋다고 생각한다.

결국 좋은 코드를 작성하려면 상황을 잘 파악해야 된다고 생각한다.