02_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가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

---

  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

Advanced

---

피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다.
재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

수도코드

---

기존에 사용하던 방식인
function fibonacci(n) {
	if(n<=1) return n;
  	return fibonacci(n-1) + fibonacci(n-2);
};
이 방식은 코드는 간단하나,
이미 계산했던 값도 새롭게 함수를 불러서 계산하기 때문에
동일한 문제가 다시 계산되는 단점이 있다.
따라서 이번에는 결과값을 따로 저장하는 빙식으로 답을 구해본다.

Code

---

function fibonacci(n) {
	// TODO: 여기에 코드를 작성합니다.
  // 피보나치 값을 저장하는 배열 fiboMemo 생성
  let fiboMemo = [0,1];
  // 피보나치 값을 계산하고 배열에 넣어주고 불러오는 함수 result 생성
  const result = (n) => {
    // 만약 n값 위치에 숫자가 존재한다면 해당 값을 불러온다(중복계산이 필요하지 않음) 
  	if(fiboMemo[n] !== undefined) return fiboMemo[n]
    // 없다면 n값에 -1,-2를 해주어서 이전 숫자 값이 있는 부분까지 쪼개어 계산 / 배열에 추가한다.
    else {
    	fiboMemo[n] = result(n-1) + result(n-2);
    }
    // 위와 같은 과정 반복 후 해당 값을 불러온다.
    return fiboMemo[n];
  }
  // 상기의 함수 실행
  return result(n);
}

키워드

• undefined