[ Coplit ] - 22_fibonacci 문제 풀이

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n

number 타입의 n (n은 0 이상의 정수)

출력

number 타입을 리턴해야 합니다.

주의 사항

재귀함수를 이용해 구현해야 합니다. 반복문(for, while) 사용은 금지됩니다. 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

 

코드 / 풀이

function fibonacci(n) {
  let newArr = [0, 1]; 
  const fib = (n) => {
    if (newArr[n] !== undefined){ 
      return newArr[n]; 
    }
    newArr[n] = fib(n - 1) + fib(n - 2); 
    return newArr[n];
  }; 
  return fib(n); 
}

1. 먼저, newArr 배열을 선언합니다.

이 배열은 각 항목이 피보나치 수열의 n번째 항목까지의 값이 저장되는 배열입니다.

 

2. 여기서 newArr[0]은 0, newArr[1]은 1로 초기화됩니다.

 

3. 다음으로, fib 함수를 정의합니다.

fib 함수는 현재 인자로 전달된 n값에 대한 피보나치 수열의 값이 이미 newArr에 저장되어 있는지 확인합니다.

 

4. 만약 newArr[n]이 이미 정의되어 있다면, newArr[n]을 반환합니다.

 

5. 만약 newArr[n]이 아직 정의되지 않았다면, newArr[n]을 fib(n - 1) + fib(n - 2)로 계산하고, newArr[n]에 해당 값을 저장한 후 반환합니다.

 

6. 마지막으로, fibonacci 함수는 n에 대한 fib(n)의 값을 반환합니다.

 

이렇게 fib 함수를 재귀적으로 호출하면서 이전에 계산한 값을 newArr에 저장하여 중복 계산을 피함으로써, 효율적으로 피보나치 수열의 값을 구할 수 있습니다.