문제 이해하기
숫자 하나를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 숫자를 n이라고 부르겠습니다.
이 함수는 피보나치(Fibonacci) 수열의 n번째 항을 반환해야 합니다.
예시
fibonacci(10) → 55
fibonacci(3) → 2
fibonacci(6) → 8
fibonacci(2) → 1
접근 방법
피보나치 수열은 첫 두 항이 모두 1이며, 그 이후의 각 항은 바로 앞의 두 항을 더한 값으로 정의됩니다. 즉, 수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... 와 같이 진행됩니다.
따라서 초기값 [1, 1]을 가진 배열을 만들고, 반복문을 통해 앞의 두 항을 더한 값을 차례대로 추가한 뒤, 마지막에 n번째 항을 반환하면 됩니다. 이 방식은 시간 복잡도 O(n)으로 매우 효율적입니다.
코드 예제
const fibonacci = (num = 1) => {
const series = [1, 1];
for (let i = 2; i < num; i++) {
const a = series[i - 1];
const b = series[i - 2];
series.push(a + b);
};
return series[num - 1];
};
console.log(fibonacci(10));
console.log(fibonacci(6));
console.log(fibonacci(3));
console.log(fibonacci(2));출력 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
55
8
2
1
동작 원리
코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
먼저 series 배열을 [1, 1]로 초기화하여 피보나치 수열의 첫 두 항을 저장합니다. 그다음 반복문이 인덱스 2부터 num-1까지 실행되면서, 각 단계마다 바로 앞의 두 항(series[i - 1]과 series[i - 2])을 더해 배열 끝에 추가합니다.
배열의 인덱스는 0부터 시작하므로, n번째 항은 series[num - 1]에 위치하게 됩니다. 예를 들어 fibonacci(10)을 호출하면 배열에 10개의 항이 저장되고, 인덱스 9의 값인 55가 반환됩니다.
참고로 기본 매개변수(default parameter)를 num = 1로 설정했기 때문에, 인수 없이 호출하더라도 오류 없이 첫 번째 항인 1을 반환합니다.