Leetcode Dynamic Programming 정복 커리큘럼

좋은 솔루션을 접하지 않은 채로 여러 문제를 풀어보다보면 논리가 계속 꼬이고 코드가 복잡해지는것을 느낄 수 있을 것이다. 아래 영상은 Dynamic programming 문제들을 5가지 패턴으로 유형화하여 제시한다. 

 

생각의 논리 전개는 다음과 같이 진행하는게 좋다. 

Step1. 간단한 예시를 이용해 Brute-force decision tree 그려보기 -- 이때 주로 time complexity 가 O(n). 그 후 타임아웃이 뜰 것을 염두에 두면서 recursive function을 구현해보기. 

Step2. 그린 Decision tree 예시를 보면서 겹치는 연산을 찾아내기. 이를 memoization 할 방법을 고민해보기. 1-d array 일수도, 2-d array 일 수도 있다. 인덱싱에서 꼬이지 않게 유의하고, array 각 칸의 의미를 잘 생각해보기. (특히 0과 1 같은 코너케이스의 의미)

Step3. Space complexity 도 더 줄이고 싶다면 bottom up 방법 고민해보기. 오른쪽에서 왼쪽으로, 아래에서 위로 역산한다.

대충 솔루션만 보고 넘기지 않고 적은 문제를 풀더라도 이 세스텝을 모두 구현해보는게 좋다. 

 

https://www.youtube.com/watch?v=mBNrRy2_hVs&t=41 

 

 

이 아래는 내가 짠 솔루션 코드를 공개한다.

 

70.Climbing Stairs

 

 

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        # bottom up
        a, b = 1, 2
        for i in range(n-2, 0, -1): #n-3, ..., 0
            new_b = a + b
            a = b
            b = new_b
        return b

        
#         # recursive & memoization

#         stairs_array = [0] + [None for _ in range(n)]
#         stairs_array[1] = 1
#         stairs_array[2] = 2
        
#         def stairs(n):
#             if stairs_array[n-1] is None:
#                 stairs_array[n-1] = stairs(n-1)
#             if stairs_array[n-2] is None:
#                 stairs_array[n-2] = stairs(n-2)
#             stairs_array[n] = stairs_array[n-1] + stairs_array[n-2] 
#             return stairs_array[n]
        
#         return stairs(n)

 

416. Partition Equal Subset Sum

 

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # bottom up
        dp = {0} 
        
        for i in range(len(nums)-1, -1, -1):
            new_dp = set()
            for current_sum in dp:
                new_dp.add(current_sum + nums[i])
                new_dp.add(current_sum - nums[i])
            dp = new_dp
        
        for e in dp:
            if e == 0:
                return True
        return False

 

1143. Longest Common Subsequence