피보나치 수 계산하기

피보나치 수는 첫째와 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, F_n = F_n-1 + F_n-2라는 공식으로 표현할 수 있습니다.

처음 두 항은 1이고, 그다음 항들은 2(1+1),3(1+2),5(2+3)이므로 전체 수열은 1, 1, 2, 3, 5 , 8, 13, 21 ... 형태를 띱니다.

피보나치 수는 황금 비율 등 우리 주변을 둘러싼 수많은 자연 현상과 관련이 있습니다.

n 번째 피보나치 수를 반환하는 함수 fib(n)을 작성해보세요.

예시:

          function fib(n) { /* 답안은 여기에 작성 */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
        

주의: fib (77)를 호출했을 때 연산 시간이 1초 이상 되면 안 됩니다.

가장 먼저 떠오르는 방법은 재귀입니다.

정의 자체에서 유추할 수 있듯이 피보나치 수열은 재귀를 사용해 구현할 수 있습니다.

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // 연산에 너무 많은 시간이 걸립니다!

그런데 이렇게 재귀를 사용해 구현하면 n이 커질 경우 속도가 느려집니다. fib(77)을 호출하면 CPU 리소스를 다 잡아먹어서 잠시 엔진이 멈출 수도 있습니다.

연산 속도가 느려지는 이유는 함수 호출 도중에 수많은 서브 호출이 일어나기 때문입니다. 같은 값들이 여러 번 평가되면서 이런 일이 발생하죠.

fib(5)의 계산 과정을 살펴봅시다.

          ...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...
        

fib(3)은 fib(5)와 fib(4)를 계산할 때 모두 필요합니다. 그렇기 때문에 fib(3)은 완전히 다른 두 곳에서 독립적으로 호출되고 평가되죠.

재귀 트리를 직접 살펴봅시다.

그림을 보니 fib(3)은 두 번 평가된다는 것이 좀 더 명확히 보이네요. fib(2)는 세 번이나 평가됩니다. 이렇게 재귀를 사용해 피보나치 수열을 구현하면 n이 증가하는 속도보다 전체 연산 횟수가 더 빨리 증가합니다. 77 자체는 그리 큰 숫자가 아니지만, 피보나치 수열에서 n=77일 경우엔 엄청난 수의 연산이 일어나죠.

이런 단점은 이미 평가된 값을 어딘가에 저장해놓는 식으로 최적화 할 수 있습니다. fib(3) 계산이 끝나면 이 결과를 어딘가에 저장해 놓았다가 같은 값이 필요할 때 저장된 값을 불러오는 식으로 말이죠.

또 다른 최적화 방법은 재귀가 아닌 반복문을 기반으로 하는 알고리즘을 짜는 것입니다.

n부터 시작해 숫자를 하나씩 줄이며 원하는 값을 구하는 대신 1과 2로 시작하는 반복문으로 fib(3)을 구하고, 이를 기반으로 fib(4)를 구하고, 또 이를 기반으로 fib(5)를 구하는 식으로 알고리즘을 구현할 수 있습니다. 이렇게 구현하면 이전 두 항의 값만 저장하면 되죠.

반복문을 기반으로 하는 알고리즘을 좀 더 자세히 살펴보겠습니다.

시작은 다음과 같습니다.

          // a = fib(1), b = fib(2), 처음 두 항은 1이라는 정의에 의해 이렇게 값을 할당하였습니다.
let a = 1, b = 1;

// c = fib(3), 세 번째 항은 첫 번째 항과 두 번째 항의 합입니다.
let c = a + b;

/* fib(1), fib(2), fib(3)을 구했습니다.
a  b  c
1, 1, 2
*/
        

이제 fib(2)와 fib(3)을 더해 fib(4)를 구해봅시다.

a에 기존 b를, b에 기존 c를 할당하고, c는 a와 b의 합이 되도록 합시다.

          a = b; // a = fib(2)
b = c; // b = fib(3)
c = a + b; // c = fib(4)

/* 다음과 같은 수열을 얻을 수 있습니다.
   a  b  c
1, 1, 2, 3
*/
        

같은 과정을 반복해 다음 수를 얻어봅시다.

          a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* 다음과 같은 수열을 얻을 수 있습니다.
      a  b  c
1, 1, 2, 3, 5
*/
        

목표로 하는 값을 얻을 때까지 위와 같은 과정을 반복하면 되겠죠? 이렇게 하면 재귀를 사용하는 방법보다 연산 속도도 빠르고 중복되는 계산도 없다는 장점이 있습니다.

반복문을 사용한 전체 코드는 다음과 같습니다.

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

반복문 내 i는 3부터 시작합니다. 피보나치 수열의 첫 번째 항과 두 번째 항은 a=1, b=1로 하드코딩 했기 때문입니다.

이런 접근 방법은 bottom-up 다이내믹 프로그래밍(dynamic programming, 동적 계획법)이라 부릅니다.