[Leetcode 300] Longest Increasing Subsequence

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

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

 

nums에서 elem 하나씩 지우고 오름차순인 것 확인?

1개부터 갯수를 점차 늘려보자.

 

[1] → 1

[1, 2] → 1의 다음이 2(오름차순) → 2

[1,2,1] → 1의 다음이 2(오름차순), 2의 다음은 1(아님) → 1 다음 2 다음 1(아님)

→ 2

 

지금까지 몇 개가 오름차순인지(a), 큰 값이 어떤 값인지(b), 지금 인덱스(i)

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

d(1, 0, 0), d(1, 1, 1), d(1, 0, 2), d(1, 3, 3), d(1, 2, 4), d(1, 3, 5)

 

..

 

졸면서 풀었는데 아주 좋지 않은 접근이었다.

일단 지금까지 몇 개가 오름차순인지(a)는 memoization할 값에 해당한다. 변수로 넣을 것이 아니다.

가장 큰 값을 고려할 필요는 있지만 그걸 기록하는 의미가 있을까?

10

9

2

5

3

7

101

18

이 경우, 세 번째 값 2를 살펴볼 때 10 9 2 에서 최댓값은 10이므로 10을 기록하겠다는 의도였다.

그런데 이렇게 하면 subsequence를 첫번째 원소를 포함한 것만 살펴보는 걸로 되어버린다.

10 9 2 5 3 7 까지, 최댓값이 10이라고 기록해버리면 subsequence의 최대길이가 1로 될 수 밖에 없다.

애초에 subsequence에 더 붙일 수 있는 상태라는 게 그 값이 최대값이 된다는 말이다. 굳이 따로 기록할 필요도 없다.

1	3	6	7	9	4	10	5	6
1	2				3		4	5
		3	4	5		6

이 경우 LIS = 6

..

 

Dynamic Programming

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = []
        for n in nums:
            new_cnt = 1
            for cnt, value in zip(d, nums):
                # incrasing and longest
                if value < n and new_cnt < cnt+1:
                    new_cnt = cnt+1
            d.append(new_cnt)
        return max(d)

 

각 nums의 원소들마다 가질 수 있는 subsequence 최대 길이를 찾아본다.

먼저 확인한 subsequence에 이어 붙일 수 있을 때(그 subsequence의 최댓값보다 큰 값일 때) 해당 subsequence의 길이보다 하나 더 긴 길이로 기록할 수 있다. 그 subsequence는 확인했던 것들 중 가장 긴 길이여야 한다.

subsequence의 최댓값은 결국 n이므로 따로 할당하지는 않고 zip을 이용해서 확인했다.

 

복잡도

Time)

nums의 원소를 한 번씩 다 확인하는데,

그 때마다 순서대로 확인한 subsequence들을 확인한다. 1+2+3+...+(n-1) = n(n-1)/2 결국 O(N^2)

 

Space)

공간 복잡도는 O(N)이다. 

 

Python - zip

d = [1, 2, 3]
t = [4, 5, 6, 7, 7]
for a, b in zip(d, t):
	print(a, b)

출력 결과

1 4
2 5
3 6

두 list중 길이가 짧은 것에 맞춰 for문이 돌아가기 때문에 매번 for문이 n번 도는 것이 아니라, 계산한 subsequence 길이들만 확인할 수 있다.

 

 

Binary Search

O(NlogN)으로 하려면 세그먼트 트리를 이용하는 방법, lower bound 이용하는 방법이 있다.

DP의 경우 모든 원소별로 어떤 subsequence에 이어 붙이는 게 가장 최선인지 탐색하느라, 결국은 효율적으로 다 확인하는 과정이라 N^2인데 NlogN으로 만드는 두 가지 방법은 모두 LIS를 직접 만들어가는 느낌이다.

 

+ 세그먼트 트리?

매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 업데이트하는 방식으로 하면 된다.

라고 하는데 잘 이해 안감...

 

LIS라는 게 결국 원소가 오름차순으로 있어야 하고, 최대한 많은 갯수가 있어야 하는데, 그러려면 맨 앞의 원소가 작을 수록 뒤에 더 많은 원소들이 올 수 있게 된다.

10

9

2

5

3

7

101

18

예를 들어 이 구성에서 subsquence를 만든다고 할 때 첫 번째 원소로 10을 고르는 것 보단 2를 고르는 게 뒤에 올 수 있는 원소들이 많아지는 길이다.

이런 아이디어로 LIS를 만들어가는 과정에 binary search를 활용하는 방법이다.

5	2	1	4	3	5
5
2
1
1	4
1	3
1	3	5

원소를 하나 하나 돌면서, 새로운 배열(subsequence 저장할)에 업데이트 한다.

5보다는 2가 있는 게 뒤에 더 많은 원소들을 끌어올 수 있다. (2보다는 1)

4는 1보다 크므로 Increasing Subsequence를 만들기 위해서는 그냥 이어 붙이면 되는 거다.

1 < 3 < 4에서, 4보다는 3이 있는 게 뒤에 더 많은 원소를 끌어올 수 있으므로 업데이트한다.

이런 식으로 만들어보면, 길이 3인 Increasing Subsequence {1, 3, 5}를 가져올 수 있다.

이 방법으로 진행해 도출한 배열이 LIS라는 보장은 없다.(는데 왜 그런지는 모르겠다. LIS가 여러 개 일수도 있는데 그 중 하나는 도출하는 것이 아닌가?)

from bisect import bisect_left


class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x = [nums[0]]
        for n in nums:
            if n > x[-1]:    # append
                x.append(n)
            else:            # update
                idx = bisect_left(x, n)
                x[idx] = n
        return len(x)

 

복잡도

Time)
nums의 원소를 한 번씩 다 확인하는데, 이 원소가 x에서 어떤 자리에 갈 수 있을지 lower bound를 binary search를 통해 찾는 과정에서 O(logN) 이므로 결국 O(NlogN)이다.

Space)

x를 만들기 때문에 O(N)

 

두 가지 방법 실행 비교

1. Dynamic Programming
   Runtime: 60 ms, faster than 97.22% of Python online submissions for Longest Increasing Subsequence.
   Memory Usage: 13.6 MB, less than 93.59% of Python online submissions for Longest Increasing Subsequence.
2. Binary Search
   Runtime: 2448 ms, faster than 64.66% of Python online submissions for Longest Increasing Subsequence.
   Memory Usage: 14.1 MB, less than 6.71% of Python online submissions for Longest Increasing Subsequence.

Dynamic Programming은 같은 코드를 두 번 돌렸는데,, 조금 다르게 나왔다. 풀 수 있는 방법들 자체의 공간 복잡도는 다 O(N)일 것 같은데, 그래서인지 적은 차이인데도 백분율 퍼센티지는 큰 차이가 난다. 실행시간은 확실히 O(NlogN)이 빠르긴 하다.

 

참고 사이트

https://ponyozzang.tistory.com/578

Python for문 변수 2개 사용 방법

https://jason9319.tistory.com/113

[최장 증가 수열] LIS(Longest Increasing Subsequence)

https://seungkwan.tistory.com/8

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

→ Binary Search 통해 LIS의 원소구성까지 찾을 수 있는 방법 포함

 

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree

[자료구조] 세그먼트 트리 (Segment Tree)

https://st-lab.tistory.com/138

[백준] 2565번 : 전깃줄 - JAVA [자바]

https://nicotina04.tistory.com/167

최장 증가 부분 수열 LIS(Longest Incresing Sequence)