알고리즘: fibonacci

Kyoorim LEE·2022년 6월 27일
0

알고리즘TIL

목록 보기
9/40

문제

아래와 같이 정의된 피보나치 수열 중 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) {
  // TODO: 여기에 코드를 작성합니다.
  // 동적 계획법??? 
  let newArr = [0, 1]; // 0번쨰와 1번째 요소는 고정시키기

  let fib = (n) => { // 함수 1개 선언
    if(newArr[n] !== undefined) {
      return newArr[n]; // 기존꺼 리턴
    }
    newArr[n] = fib(n-1) + fib(n-2); // 새로운 합
    return newArr[n]
  }
  return fib(n);
}

한 줄 평

  • 재귀함수를 이용하여 풀었더니 시간초과가 나왔다
function fibonacci(n) {
if (n <= 1) {
  return n;
	};
  return fibonacci(n-1) + fibonacci(n-2);
}
  • newArr 선언을 통해 0번째와 1번째를 고정시킨다는 것
  • 레퍼런스 풀이가 사실 너무 어려워서 다시 풀 수 있을지 모르겠다.. 그냥 머리속에 넣어놔야할듯
profile
oneThing

0개의 댓글