LeetCode: 300. Longest Increasing Subsequence

1. 가장 간단한 DP 형태

O(N**2)이다. 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = 1
        for i in range(1, len(nums)):
            temp = -1
            j = i - 1
            while j >= 0:
                if nums[j] < nums[i]:
                    temp = max(temp, dp[j])
                j -= 1
            if temp != -1:
                dp[i] = temp + 1
            else:
                dp[i] = 1
        return max(dp)

O(N**2)답게 빠르지 않다. 개선을 해보자.

 

2. LIS 알고리즘

(1)의 알고리즘은 하나의 숫자에 대해 계산함에 있어 이전에 나온 모든 숫자를 다 조사한다.

그러다보니 N개의 숫자에 대해 최대 N개의 숫자를 다 조사하기 때문에 O(N**2) 알고리즘이다.

아래 방법을 사용하면 O(N*logN)알고리즘으로 구현이 가능하다.

================================================

dp에 오름차순으로 숫자를 쌓아가되, 마지막 숫자보다 작은 숫자를 만나면

해당 숫자가 dp에 들어갈 위치를 이진탐색으로 찾고, 그 위치에 넣는다.

================================================

설명이 좀 복잡하다면 코드를 확인하자.

from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [nums[0]]
        for i in range(1, len(nums)):
            idx = bisect_left(dp, nums[i])
            if idx == len(dp):
                dp.append(nums[i])
            else:
                dp[idx] = nums[i]
        return len(dp)