[5부 알고리즘] 23장 다이나믹 프로그래밍

📌 85) 피보나치 수 ( 리트코드 509. Fibonacci Number )

✔ 풀이1 (재귀 구조 브루트 포스)

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

✔ 풀이2 (메모이제이션)

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

✔ 풀이3 (타뷸레이션)

from collections import defaultdict
class Solution:
    dp = defaultdict(int)
    
    def fib(self, n: int) -> int:
        #defaultdict을 사용했기 때문에 dp[0] = 0
        self.dp[1] = 1
        for i in range(2, n + 1):
            self.dp[i] = self.dp[i - 1] + self.dp[i - 2]
        
        return self.dp[n]

✔ 풀이4 (두 변수만 이용해 공간 절약)

#메모이제이션, 타뷸레이션 방법보다 공간복잡도를 줄임
#딕셔너리 말고 2개의 변수만 사용
class Solution:
    def fib(self, n: int) -> int:
        x, y = 0, 1
        for _ in range(n):
            x, y = y, x + y
        return x

📌 86) 최대 서브 배열 ( 리트코드 53. Maximum Subarray )

✔ 풀이1 (메모이제이션)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            #이전 값이 0보다 클 경우 더함, 또 그 값이 0보다 크면 그 다음값에 더함...(반복)
            nums[i] += nums[i - 1] if nums[i - 1] > 0 else 0
        return max(nums)

✔ 풀이2 (카데인 알고리즘)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best_sum = float('-inf')
        current_sum = 0
        for num in nums:
            current_sum = max(num, num + current_sum) #더 큰 값을 기억
            best_sum = max(best_sum, current_sum)    #매번 최대값 판별하여 저장
        return best_sum

📌 87) 계단 오르기 ( 리트코드 70. Climbing Stairs )

✔ 풀이1 (재귀 구조 브루트 포스) Time Limit Exceeded

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

✔ 풀이2 (메모이제이션)

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

📌 88) 집 도둑 ( 리트코드 198. House Robber )

✔ 풀이1 (재귀 구조 브루트 포스) Time Limit Exceeded

class Solution:
    def rob(self, nums: List[int]) -> int:
        def _rob(idx): #해당 idx까지 있을 때 훔칠 수 있는 돈의 최대값을 return
            if idx < 0:
                return 0
            
            return max(_rob(idx - 1), _rob(idx - 2) + nums[idx])
        return _rob(len(nums) - 1)

✔ 풀이2 (타뷸레이션)

from collections import defaultdict
class Solution:
    def rob(self, nums: List[int]) -> int:
        
        if len(nums) < 2:
            return nums[0]
        
        dp = defaultdict(int)  #dp[i] = i지점까지 훔친 돈의 최대 액수
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        for i in range(2, len(nums)): 
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        
        return dp[len(nums) - 1]