박종훈 알고리즘 블로그

(Leetcode) 300 - Longest Increasing Subsequence

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


https://leetcode.com/problems/longest-increasing-subsequence/description/

이 문제는 DP 문제이다.

해결 코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        longest = 1
        
        dp = [1] + ([float('-inf')] * (len(nums) - 1))

        for i, num in enumerate(nums):
            if i == 0:
                continue
            for j in range(0, i + 1):
                if num > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            
            if dp[i] == float('-inf'):
                dp[i] = 1

            longest = max(longest, dp[i])

        return longest

풀이

이 문제는 이전 값을 활용할 수 있는 문제이다.

explanation page1 explanation page2 explanation page3 explanation page4 explanation page5 explanation page6

다른 사람의 코드

이 코드는 간결하고, 속도도 빠르게 나온다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lst = []
        for num in nums:
            i = bisect_left(lst, num)
            
            if i == len(lst):
                lst.append(num)
            
            else:
                lst[i] = num
        
        return len(lst)

bisect_left 이 뭐하는 애인가 싶어서 찾아보니 다음과 같았다.

bisect - 출처 : docs.python.org

bisect 는 배열 이진 분할 알고리즘 구현체이고 bisect_left는 정렬된 순서를 유지하도록 a에 x를 삽입할 위치를 찾아준다고 한다.

print(Solution().lengthOfLIS([0,1,0,3,2,3]))
num: 0
i: 0
append 0
lst [0]

num: 1
i: 1
append 1
lst [0, 1]

num: 0
i: 0
lst[i] = 0
lst [0, 1]

num: 3
i: 2
append 3
lst [0, 1, 3]

num: 2
i: 2
lst[i] = 2
lst [0, 1, 2]

num: 3
i: 3
append 3
lst [0, 1, 2, 3]

4 # 최종결과