효율적인 피보나치
웹 개발/Algorithm 2021. 3. 15. 09:08더보기
문제
아래와 같이 정의된 피보나치 수열 중 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, memo = []) {
// TODO: 여기에 코드를 작성합니다.
if(memo[n] !== undefined) return memo[n];
// 이미 해결한 하위 문제인지 찾아본다
if(n === 0) return 0
if(n <= 2) return 1;
let res = fibonacci(n-1, memo) + fibonacci(n-2, memo);
// 없다면 재귀로 결과값을 도출하여 res 에 할당
memo[n] = res;
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
return res;
}