Leetcode: Longest Increasing Subsequence (LIS: 최장 증가 부분 수열)

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

integer array가 주어졌을때, 최장 증가 부분 수열을 구하는 문제이다. 

아래와 같이 DP를 이용해서 풀 수 있다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0] * len(nums) # dp[i]: nums[i]를 마지막 수로 가지는, LIS의 길이
        answer = 0
        for i, n in enumerate(nums):
            dp[i] = 1
            for j in range(i-1, -1, -1):
                if nums[j] < n:
                    dp[i] = max(dp[i], dp[j]+1)
            answer = max(answer, dp[i])
            
        return answer

dp[i]가 의미하는 바는, nums[i]를 마지막 수로 가지는 LIS의 길이이다. 0부터 len(nums)-1까지 루프를 돌며 dp를 채워나간다. dp[i]는, nums[i]보다 작은 값을 마지막 수로 가지는 LIS의 길이 중 max +1이다. 이를 위해, dp[i]를 구할 때, dp[0]~dp[i-1]까지 보는 과정이 필요하므로, 이 방법은 O(n^2)의 time complexity를 가진다.

 

조금 더 나은 방법은 binary search를 이용하는 것이다. 

마찬가지로 0부터 len(nums)-1까지 루프를 돌며 nums를 확인하는데, 각 num마다 binary search로 dp array에 들어갈 자리를 찾는다. 찾은 자리가 현재 dp의 길이와 같다는 것은 dp안에 있는 모든 원소보다 num이 크다는 의미이므로, 수열이 증가할 수 있다. 그러므로 dp에 추가한다. 

찾은 자리가 dp에 존재하는 인덱스인 경우, 그 값을 새로운 값으로 바꿔치기한다. 예를 들어, 현재 dp가 [1,3,5]였고, num이 4였다면, binary search를 통해 찾은 num이 들어갈 인덱스는 5의 자리인 2이다. 그러므로 dp는 [1,3,4]가 된다. 이로 인해, 만약 이후에 5와 같은 숫자가 나타났을 때, 기존 [1,3,5]에서는 그 값을 추가할 수 없지만, 업데이트 된 [1,3,4]에서는 그 값을 추가할 수가 있게 된다. 

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

        return len(dp)

 

예를 들어, [10,9,2,5,3,7,101,18] 의 경우를 살펴보면, 아래와 같이 진행된다.

i	0	1	2	3	4	5	6	7
nums[i]	10	9	2	5	3	7	101	18
dp	[10]	[9]	[2]	[2,5]	[2,3]	[2,3,7]	[2,3,7,101]	[2,3,7,18]

최종적으로 모든 원소에 대해 루프를 돈 뒤의 dp의 길이가 LIS의 최소 길이이다.

 

다만 주의해야 할 점은, 이 알고리즘을 통해 얻어진 dp는 실제 LIS가 아니라는 것이다.

예를 들어, [2,3,4,5,1]의 경우를 살펴보자.

 

i	0	1	2	3	4
nums[i]	2	3	4	5	1
dp	[2]	[2,3]	[2,3,4]	[2,3,4,5]	[1,3,4,5]

위의 예시, 즉 [2,3,4,5,1] 에서의 LIS는 [2,3,4,5]로, 그 길이는 4이다. 위의 알고리즘을 통해 구한 결과 dp의 길이도 4로 LIS의 길이는 구할 수 있지만, 마지막 스냅샷 dp는 [1,3,4,5]로, 1은 5의 뒤에 있으므로 이는 실제 LIS가 아니다. 

즉, 위의 알고리즘은 LIS의 길이를 알아낼 때에만 쓰여야 한다. 

 

 

링크: leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode