LeetCode - fibonacci number

katanazero86·2020년 6월 2일
0

leetcode

목록 보기
9/13
post-thumbnail

fibonacci number

  • Difficulty : easy

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

  • 피보나치 수열 구현하기. N 이라는 숫자값이 주어지면 N 까지의 수열값 구하기
  • N : 3 -> 0 + 1 + 1 = 2

solution

  • 작성 언어 : javascript
  • Runtime : 92 ms
/**
 * @param {number} N
 * @return {number}
 */
var fib = function fibonacciNumber(N) {
    
    if(N <= 1) {
        return N;
    }
        
    return fibonacciNumber(N-1) + fibonacciNumber(N-2);
        
};
  • 재귀호출로 쉽게 해결이 가능하며, 함수표현식을 재귀적으로 사용하려면 이름을 부여하면된다.(기명함수표현식)
  • f(N-1) + f(N-2); 를 기억하면 쉽게 해결이 가능
  • 기저조건은 N <= 1 값일 때, N 을 반환해주면 된다.
  • 재귀호출이므로, 이걸 무한히 호출하면 stack overflow 가 발생할 확률이 높다.
  • Runtime : 64 ms
/**
 * @param {number} N
 * @return {number}
 */
var fib = function fibonacciNumber(N, before = 0, after = 1, sum = 0) {
        
    if(N === 0) return sum;
    if(N === 1) return sum ? sum : 1;
    
    sum = before + after;  
    return fibonacciNumber(N-1, before = after, after = sum, sum = sum);
};
  • 꼬리재귀(tail recusion) 형태로 코드 수정
profile
developer life started : 2016.06.07 ~ 흔한 Front-end 개발자(현재는 백수 얏호👻)

3개의 댓글

comment-user-thumbnail
2020년 6월 7일

피보나치를 재귀로 호출하는 경우에 함수 안에 함수를 계속해서 쌓아나가게 되기 때문에 (결국은 return되는 1의 합의 형태이므로, Fn을 호출하기 위해서 Fn개의 함수 스택이 쌓임) Maximum stack size exceed 에러가 터지기 쉽습니다. DP나 일반식으로 풀어보시는 것도 괜찮을 것 같네용

# Fibonacci example - general solution
class Solution:
    def getFibonacci(self, n: int) -> int:
        if(n==0 or n==1):
            return 1
        return round((pow(((1+math.sqrt(5))/2),n+1) - pow(((1-math.sqrt(5))/2),n+1))/math.sqrt(5))
        
1개의 답글