LeetCode 509 Fibonacci Number | Python | Memoization

bokdol11859·2021년 12월 2일
0

그동안 백준만 풀었었는데, 백준은 코테 대비보단 대회 대비에 조금 더 가까운 것 같아서 유명한 리트코드를 한번 시도해보기로 했다.
난 대회는 나갈 생각이 없기 때문이다,,

다가오는 알고리즘 분석 시험 대비도 할겸, 내가 가장 자신 없어하는 다이나믹 프로그래밍을 연습해보기로 마음 먹었다..!

이런식으로 내가 원하는 주제의 문제들을 모아놓은 Study Plan이 있는데, 풀어야 하는 문제들이 정해져 있어서 무슨 문제를 풀어야 할지 고민하지 않아도 되는 점에서는 정말 좋은 것 같다.

아무튼 1일차부터 시작을 해야하니, 첫 문제는 509번 Fibonacci Number (피보나치 숫자)를 한번 풀어보려고 한다!

문제 설명을 보면, 피보나치 수열이 무엇인지 알려주고, n이 주어졌을 때, 피보나치 수열에서 n번째 숫자를 구하라는게 문제인데,,

사실 이 문제같은 경우에는 푸는 방법이 너무나도 많다.. 쉽게 풀려면 쉽게 풀수도 있겠지만, 그러면 연습이 되지 않을 것 같아서, 조금 다이나믹하게 풀어보려고 한다!

참고로

사실 n의 범위가 되게 작기 때문에 사실 쉽게 풀어도 되긴 한다

아무튼 시작을 해보자면, 나는 메모이제이션 기법을 이용해서 한번 풀어보려고 한다.

메모이제이션 (Memoization) 기법이란:
컴퓨터가 동일한 연산을 여러번 해야하는 상황에서, 연산의 결과값을 저장해서 다음에 동일한 연산을 다시 해야할 때, 컴퓨터를 갈궈서 연산을 하는게 아닌, 그냥 저장된 값을 그냥 가져오는 것이 메모이제이션 기법이다.

뭔가 말로 하니까 어렵긴 한데, 간단히 예를 들어보자.

피보나치 수열은 다들 알겠지만,

F(0) = 0, F(1) = 1

이렇게 수열의 0번째 값은 0, 1번째 값은 1이라는 것을 알고 있을때, 2번째 값(n)부터는 이전값(n-1)과 이전이전값(n-2)의 합이 된다. 이런 패턴이 계속 이어지는걸 보고 피보나치 수열이라고 하는데,
잘 생각을 해보면, 동일한 연산이 여러번 발생하는 것을 알수있다.

예를 들어서 F(4)를 구하려면 F(3)과 F(2)를 구해야하고, F(3)을 구할때는 또 F(2)와 F(1)을 구해야 하는데, 여기서 F(2) 를 구하는 연산이 벌써 중복된다는 사실을 알수가 있다.

F(2)는 어렵지 않게 F(1) + F(0)이라서 1이라는 사실을 알 수가 있다. 이제 그럼 F(2), F(1), F(0)를 오름차순으로 배열에 저장을 해보자.

dp = [0,     1,      2]
     F(0),  F(1),  F(2)

만약 F(2)를 또 구해야 하는 상황이 온다면, 그 이후부턴 다시 F(1) + F(0)를 연산을 하는게 아닌, 그냥 dp배열에서 2번째 값을 가져오면 불필요한 연산이 줄어들게 된다.

이전에 연산을 통해 구한 값을 저장해서 필요할 때 다시 꺼내오는걸 보고 메모이제이션 기법이라고 한다!

이쯤되면 아니 그걸 그냥 계산하면 되지 뭘 그렇게 귀찮게 계산하고 배열에 저장하고 다시 가져오고 하냐 라는 의문이 들수도 있다.

내가 그렇게 생각했었다.

메모이제이션을 사용하는 이유는 정말 간단하다!

피보나치 수열에서 숫자가 커지면 커질수록 필요한 연산의 횟수가 기하급수적으로 늘어나게 되는데, 이걸 하나하나 다 계산하면 아무리 좋은 컴퓨터라도 시간이 오래걸린다.
숫자가 작다면 시간제한내에 문제를 풀수도 있겠지만, 숫자가 커지면 그냥 무작정 계산하는 방법으로는 절대로 문제를 풀수가 없다.

자 이제 본격적으로 문제를 풀어보자!

우선 메모이제이션 기법을 이용하기 위해서 dp테이블을 만들어준다.

dp = [-1] * 31

문제에 주어지는 범위는 0 <= n <= 30인데, 0부터 30까지 모든 값을 저장하려면, 31개의 저장공간이 필요하다. 그래서 dp테이블을 31사이즈를 갖도록 세팅을 해주고, 모든 값들을 -1로 지정을 해준다.

그리고, 피보나치에서 기본적으로 0번째 값은 0, 1번째 값은 1이기 때문에

dp[0] = 0
dp[1] = 1

이런식으로 0번째랑 1번째값을 지정해준다.

그러면 이제 dp테이블이

[0, 1, -1, -1, ..., -1]

이렇게 되어있을텐데, 기본 세팅은 끝이 났고, 이제부터 본격적으로 알고리즘을 짜본다.

우리가 현재 아는 피보나치 숫자들은 단 두개이다. F(0), F(1).

그러면, 우리가 알고리즘에서 지금 리턴할 수 있는 값은
F(0), F(1) 두개라는 뜻이다. 다른 말로는 Base Case로 부른다.

그러면 Base Case에 알고리즘이 도달했을 때, 각 값들을 리턴해주게 만들면,

if n == 0 or n == 1: return dp[n]

이런식으로 구현을 할수가 있다.

그 다음으로 확인해야 하는건 n번째 값이 이미 연산이 된적이 있냐 없냐이다. 만약 n번째 값이 이미 연산이 되었다면 메모이제이션 기법을 이용중이기 때문에 그냥 바로 리턴을 하면 된다.

if dp[n] != -1: return dp[n]

이부분 또한 이런식으로 구현을 할수가 있다.

마지막으로, 만약 n이 0이나 1도 아니고, 연산이 된적도 없다면 어떻게 해야할까?

위에 선언해놓은 조건들에 부합할때까지 재귀적으로 함수를 호출하면 된다.
1. n이 0이나 1이 될때까지 n을 줄여나가면서 재귀적으로 함수를 호출한다
2. dp[n]이 -1이 아닐때까지 n을 줄여나가면서 재귀적으로 함수를 호출한다.

여기서 가장 중요한 부분은 재귀적으로 함수를 호출한다는 점이다.

else:
    dp[n] = self.fib(n-1) + self.fib(n-2)
    return dp[n]

원래 self.fib()이 아니라 그냥 fib()으로 해도 되는데, 리트코드는 클래스 형식으로 코드를 짜야 하기 때문에 어쩔 수 없이 self.fib()으로 했다.
그냥 백준할걸

아무튼 이게 끝이다! 피보나치 문제는 사실 어려운 문제가 아니라서 쉽게 풀라면 정말 쉽게 풀수있지만 그렇게되면 숫자가 커지면 코드가 너무 오래걸리기도 하고, 다이나믹 프로그래밍을 연습하는게 목적인 만큼 다이나믹하게 문제를 한번 풀어보았다!

전체코드:

class Solution:
    def fib(self, n):
        dp = [-1] * 31
        dp[0] = 0
        dp[1] = 1
        if n == 0 or n == 1:
            return dp[n]
        elif dp[n] != -1:
            return dp[n]
        else:
            dp[n] = self.fib(n-1) + self.fib(n-2)
            return dp[n]
        

문제 해결~~ 리트코드는 이렇게 시간과 메모리 사용량도 보여준다!

아니 근데 이렇게 했더니 n 범위가 작아서 그런지 런타임이 엄청 느리네

아무리 생각해도 너무 이상할 정도로 느린 것 같아서 좀 알아봤더니:

from functools import lru_cache
class Solution:
    @lru_cache(None)
    def fib(self, n):
        dp = [-1] * 31
        dp[0] = 0
        dp[1] = 1
        if n == 0 or n == 1:
            return dp[n]
        elif dp[n] != -1:
            return dp[n]
        else:
            dp[n] = self.fib(n-1) + self.fib(n-2)
            return dp[n]

이런식으로 @lru_cache(None)이라는걸 추가해주면 속도가 훨씬 더 빨라진다!

profile
코딩을 좋아하는 개발자

0개의 댓글