[99클럽 코테 스터디] 9일차 TIL - 동적계획법, Fibonacci Number

[9일차] 동적계획법

 

문제: https://leetcode.com/problems/fibonacci-number/description/

* 대충 번역: 주어진 n에 대하여, F(n)을 반환하라. F(n) = F(n-1) + F(n-2) (n > 1) 이다.

Solution

피보나치 수열은 재귀 함수와 메모이제이션 두 가지 방법으로 해결할 수 있다. 나는 재귀 함수로 구현했다.

2023.07.14 - [Algorithm] - [Python/코테] 다이나믹 프로그래밍(1) - 개념, 피보나치 수열 구현, 메모이제이션

[Python/코테] 다이나믹 프로그래밍(1) - 개념, 피보나치 수열 구현, 메모이제이션

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib(n-1) + self.fib(n-2)

Better Solution

한 번 계산한 결과를 메모리에 기록(memo)해두는 메모이제이션 방법으로, 더 효율적이다.

배열이 아닌 사전형 변수를 사용한 이유는, 배열과 다르게 사전형은 동적 크기로 사용할 수 있고 초기화가 필요하지 않기 때문이다. 

memo = {0: 0, 1: 1}

class Solution(object):
    def fib(self, n):
        if n in memo: return memo[n]
        memo[n] = memo[n - 1] + memo[n - 2]
        return memo[n]

배열을 사용하려면 아래와 같이 구현할 수 있다. 배열의 크기를 미리 정하고, 초기화도 해주어야 한다. 대신 인덱스를 활용하여 빠른 접근이 가능하다.

class Solution(object):
    def fib(self, n):
        if n == 0: return 0
        if n == 1: return 1
        
        # 배열 크기를 n+1로 설정
        memo = [0] * (n + 1)
        memo[1] = 1
        
        for i in range(2, n + 1):
            memo[i] = memo[i - 1] + memo[i - 2]
        
        return memo[n]

나다어

• 동적계획법은 DP 테이블을 활용하는 메모이제이션 기법을 활용하여 해결할 수 있다.
• 초기화와 고정 크기라는 배열의 단점을 완화한 것이 사전형 변수이다.