[코플릿]fibonacci

코드스테이츠 과제 코드를 공부 목적으로 변형 해서 정리 하였습니다.

✅문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

 

⛔주의

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

 

💬입출력 예시

let output = fibonacci(0);
console.log(output); // --> 0

output = fibonacci(1);
console.log(output); // --> 1

output = fibonacci(5);
console.log(output); // --> 5

output = fibonacci(9);
console.log(output); // --> 34

 

🍀해결코드

function fibonacci(n) {
  const memo = [0, 1];
  const aux = (n) => {
    if (memo[n] !== undefined) return memo[n];
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
}​

---

🦦해설

평소 피보나치를 해결하는 방식으로 문제를 해결하면 통곽 되지 않았다.

function fibonacci(n){
    if(n<2) return n
    return (fibonacci(n-1)+fibonacci(n-2))
}

실행시간 초과가 걸린다

이를 해결하기 위해 다른 방법을 생각 해야한다 동적프로그램이 dp로 해당 문제를 풀어 시간 초과를 해결해야 했다.

 

memo에 0,1,을 넣었다.

피보나치에서 0번째는 0, 1번째는 1을 나타낸것을 memo로 표현했다.

재귀를 돌릴 함수인 aux를 만들었고, 다음 함수에서는 memo의 해당 순번에 값이 있다면 값을 출력한다.

없는 경우 아래로 내려가 aux(n-1)+aux(n-2)의 값을 받는다.

 

memo에 구한 피보나치를 적으므로 불필요하게 피보나치를 중복적으로 구하는 행동을 막는다.