509. Fibonacci Number

피보나치 수열이다.

2이상의 정수일 때, 인덱스 하나 전의 수와 두개 전의 수가 합쳐져서 해당 수가 만들어진다.

초기값으로 0일때 0이고 1일때 1이다.

 

---

 

solution 1. 

재귀로 푸는 방법이다.

0과 1일때는 값을 그대로 뱉고, 2보다 큰 값은 재귀로 값을 얻어낸다.

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        return self.fibo(n-1) + fibo(n-2)

 

solution 2.

메모제이션 방법이다.

2 이전은 똑같이 그대로 리턴하고 나머지 값은 값을 저장해두는 방법이다.

class Solution:
    mem = collections.defaultdict(int)
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        if self.mem[n]:
            return self.mem[n]
        
        self.mem[n] = self.fib(n-1) + self.fib(n-2)

        return self.mem[n]

이 방식이 런타임 200배 더 빠른 성능을 보여줬다.