[LeetCode 300] Longest Increasing Subsequence (with Python / DP)

문제링크

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

Longest Increasing Subsequence - LeetCode

문제설명

 

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

 

문제풀이

 

LIS(가장 긴 증가하는 부분 수열)을 구하는 문제로,

대표적인 풀이 방법으로 DP를 사용하는 것이 있다.

 

D[i]: i번째 원소까지 증가하는 수열의 길이를 저장하는 배열이라 두자.

그리고 i가 순회하는 동안 j가 i번째 까지 순회하며 해당값을 비교해 j인덱스에 위치한 원소가 더 작다면,

D[i]값을 갱신한다. 이때, 원래 존재하는 (D[i]값)과 (D[j]에 1을 더한값)을 비교하여 큰수를 저장.

 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        # 가장 긴 증가하는 수열의 길이를 출력
        # ex) [10, 9, 2, 5, 3, 7, 101, 18]
        # Can you come up with an algorithm that runs in O(nlogn)
        # D[i]는? i번째까지 증가하는 수열의 길이

        N = len(nums)
        D = [1] * N
        
        for i in range(1, N):
            for j in range(i):
                if nums[i] > nums[j]:
                    D[i] = max(D[i], D[j]+1)

        return max(D)

하지만 해당 방법으로 풀게 되면 최악의 상황에서 O(N^2)의 시간복잡도를 갖게된다.

 

따라서 O(NlogN)까지 줄일 수 있는 방법이 DP + binary search 를 활용한 방법이 있다.

 

코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        # 가장 긴 증가하는 수열의 길이를 출력
        # ex) [10, 9, 2, 5, 3, 7, 101, 18]
        # Can you come up with an algorithm that runs in O(nlogn)
        # D[i]는? i번째까지 증가하는 수열의 길이

        lis = [nums[0]]
        for num in nums:
            # 현재요소가 마지막 요소보다 큰 경우 추가 
            if num > lis[-1]:
                lis.append(num)
            else:
                l, r = 0, len(lis) - 1
                while l < r:
                    mid = (l + r) // 2
                    # 이진탐색을 통한 값
                    if lis[mid] < num:
                        l = mid + 1
                    else:
                        r = mid
                lis[l] = num
                
        return len(lis)