Longest Increasing Subsequence | LeetCode 810 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Longest Increasing Subsequence | LeetCode 810

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/810/

주어진 리스트 내 가장 긴 increasing subsequence 의 길이를 찾는 문제입니다. 

 

subsequence 란 배열에서 몇개의 요소를 삭제해서 만들 수 있는 sequnce를 말합니다. (순서는 바꾸지 않습니다)

예를들어, [2, 1, 3]의 subsequence는 아래와 같습니다.

[2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], []  

 

increasing subsequence는 subsequence 내 오른쪽 요소가 항상 모든 왼쪽 요소보다 커야 합니다.

예를들어, [2, 1, 3]의 increasing subsequence는 아래와 같습니다.

[2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], []  

 

💡 풀이

1.  Dynamic Programming - 현재값 ~ 배열 끝까지 만들 수 있는 LIS를 저장

주어진 배열을 가장 오른쪽 값부터 확인하면서

현재값 ~ 배열의 끝까지 중 만들 수 있는 LIS를 캐시에 저장합니다.

 

현재값의 LIS = 현재보다 오른쪽 값들 중 현재값보다 큰 값들의 LIS 중 가장 큰

 

ex) nums = [10, 9, 2, 5, 3, 7, 101, 18]

 

1) 18  - 뒤에 아무 숫자 없으므로 LIS는 1입니다.

 

2) 101 - 뒤에 18이 있지만 101보다 작은 수이므로 Increasing이 아닙니다. 따라서 LIS는 1입니다.

 

3) 7 - 뒤에 101과 18 모두 7보다 큽니다.

7의 LIS = max( 101의 LIS, 18의 LIS) +1= 2

[7, 101], [7, 18] 모두 7에서 시작하는 longest increasing subsequence입니다. 

 

4) 3 - 뒤에 7, 101, 18 모두 3보다 큽니다. 

3의 LIS = max( 7의 LIS, 101의 LIS, 18의 LIS) +1

             = max( 2, 1, 1) +1 = 3

[3, 7, 101] 또는 [3, 7, 18]이 3에서 시작하는 longest increasing subsequence입니다. 

 

4) 5 - 뒤에 7, 101, 18 이 5보다 큽니다.

5의 LIS = max( 7의 LIS, 101의 LIS, 18의 LIS )  +1

             = max( 2, 1, 1 )+1 = 3

[5, 7, 101] 또는 [5, 7, 18]이 3에서 시작하는 longest increasing subsequence입니다. 

 

4) 2 - 뒤에 5, 3, 7, 101, 18 이 2보다 큽니다.

5의 LIS = max( 5의 LIS, 3의 LIS, 7의 LIS, 101의 LIS, 18의 LIS)  +1

             = max( 3, 3, 2, 1, 1) = 4

[2, 5, 7, 101]

[2, 5, 7, 18]

[2, 3, 7, 101]

[2, 3, 7, 18]

이 2에서 시작하는 longest increasing subsequence입니다. 

 

 

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        print(nums)
        cache = [1]*(len(nums))
        maxValue = 0
        for i in range(len(nums)-1, -1, -1):
            for j in range(i+1, len(nums)):
                if nums[j] > nums[i]: cache[i] = max(cache[i], cache[j]+1)
            maxValue = max(cache[i], maxValue)
            # print("finding LIS for ",nums[i], "... ", cache[i], cache)
        return maxValue

 

Time Complexity
O(N^2)
각 원소마다 뒤에있는 모든 원소들의 값들을 확인해야 하므로 이중포룹 즉 O(N^2)이 됩니다. 

 

 

2. O(NlogN) 풀이

 

만들어지는 LIS길이가 같다면 더 큰 값을 기준으로 하는게 유리하다 라는 점을 활용했습니다.

LIS길이와 원소값을 캐싱해가며 삽입 위치를 logN만에 찾아가는 방식입니다.

 

bisect_left는 오름차순 배열에서 사용하는 함수라서 내림차순으로 정렬하기 위해 target_num에 음수를 취해 저장했습니다. 

 

ex) nums = [10, 9, 2, 5, 3, 7, 101, 18]

 

1) 18

LIS(18) = 1 이므로 cache[0] = -18

 

2) 101

bisect_left 를 통해 cache[0] 자리에 -101을 삽입해야 함을 알고 있음

기존에 저장되어있던 18보다 101이 더 크므로 cache[0] = -101로 업데이트

* 이후에 18~101사이에 값이 들어오면 18로는 LIS를 만들 수 없지만 101로는 만들 수 있음

[20, 18] LIS아님

[20, 101] LIS

즉, 101로 만들 수 있는 LIS는 18로 만들 수 있는 LIS를 모두 포함함

 

3) 7

bisect_left 를 통해 cache[1] 자리에 -7을 삽입해야 함을 알 수 있음.

그 자리는 비었으므로 바로 삽입.

 

4) 3

bisect_left 를 통해 cache[2] 자리에 -3을 삽입해야 함을 알 수 있음.

그 자리는 비었으므로 바로 삽입.

 

4) 5

bisect_left 를 통해 cache[2] 자리에 -5을 삽입해야 함을 알 수 있음.

기존에 저장되어있던 3보다 5가 더 크므로 cache[2] = -5로 업데이트

...

 

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        cache = []
        cacheLen = 0
        for i in range(len(nums)-1, -1, -1):
            target_num = -nums[i]
            idx = bisect_left(cache, target_num)
            if idx == cacheLen:
                cache.append(target_num)
                cacheLen += 1
            else: cache[idx] = target_num
        return cacheLen