Leetcode Fibonacci Number 파이썬 풀이

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Fibonacci Number
등급: Easy

내용: 피보나치 수.

<코드>

피보나치 수의 개념은 간단하다. 각 숫자들은 앞의 두 숫자의 합이다. 

그래서, 011235.... 이렇게 되는 숫자들이다.

 

간단하게, 그렇다면 

f(n) = f(n-1) + f(n-2)를 적으면 되는 것이다.

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

그렇다면 이런 코드가 나오게 되어있다. 

 

하지만, 이 코드의 문제점은 이미 계산한 숫자를 또 계산해야한다는 것이다. 무슨 말이냐면, 내가 8번째 숫자를 구하기 위해서, 7번째 숫자랑 6번째 숫자를 더하게 된다. 그런데, 7번째 숫자를 구하기 위해서 6번째 숫자까지 0번째 숫자부터 계산한 뒤에, 또다시 6번째 숫자를 0번째 숫자부터 구하게 된다는 것이다. 굳이 똑같은 숫자를 위해서 두 번 또는 세 번 계산할 필요 없지 않은가?

 

그래서, memoization, 메모이제이션를 활용하게 된다. 위키백과에 따르면, "이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술"이 되겠다.

이를 활용한 코드는:

class Solution(object):
    def fib(self, n):
        cache = {}
        
        def recur_fib(n):
            # if there already is fibonacci number value
            if n in cache:
                return cache[n]
            
            if n<2:
                result = n
            else:
                result = recur_fib(n-1) + recur_fib(n-2)
            
            # put the result in cache 
            cache[n] = result
            
            return result
        
        return recur_fib(n) 
        """
        :type n: int
        :rtype: int
        """

cache랑 hash table를 만들어서 계속 계산한 값을 이곳에 저장하고, 필요할 때 불러오게 하는 것이다. 

 

굉장히 간단하고 깔끔하다.

 

<총평>

프로그래밍은 공부하면 할수록 신기하고 재밌는 것 같다. 

 

Happy coding!