[Leetcode, Python] 300. Longest Increasing Subsequence 풀이

Leetcode 300번 문제

"오름차순 수열의 최대 길이"를 찾는 문제라고 생각하고 풀었다.
첫번째 시도

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [1]*N # dp[i] = index i까지의 최댓값
        
        for i in range(1, N):
            if nums[i] < nums[i-1]:
                dp[i] = dp[i-1] # index i의 값이 i-1의 값보다 작다면 증가하는 수열에 포함되지 않음
            elif nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1 # 증가하는 수열에 포함

        return max(dp)

처음에는 DP(다이나믹 프로그래밍)을 활용해서

1. nums의 i index의 값이 i-1 index의 값보다 작다면 증가하는 수열에 포함되지 않는다.
2. dp[i-1]는 index i-1까지의 최대 수열 길이를 갖기 때문에 dp[i] = dp[i-1]로 최대 수열 길이를 유지한다.
3. nums의 i index의 값이 i-1 index의 값보다 크다면 증가하는 수열에 포함한다. dp[i] = dp[i-1]+1 최대 수열 길이에 +1을 한다.

이러한 사고 흐름으로 코드를 구현했다.
그러나 24번째 tastcase에서 실패했다.

실패 테스트 케이스
input: nums = [4,10,4,3,8,9]
output: Exptected: 3

내가 구현한 코드의 흐름으로 실패 테스트 케이스를 실행하면
dp = [1,2,2,2,3,4] -> 즉, Output으로 4가 나온다.

현재 코드의 문제점
현재 방식은 '인접한 두 원소'만 비교하고 있어서, 전체 증가 수열 중에서 가장 긴 걸 찾지 못한다.

for i in range(1, N):
    if nums[i] < nums[i-1]:
        dp[i] = dp[i-1]
    elif nums[i] > nums[i-1]:
        dp[i] = dp[i-1] + 1

해당 루프는 i와 i-1만 비교하고 있다.
문제를 해결하려면 nums[0] ~ nums[i-1]까지 모든 이전 원소들 중에서 nums[i]보다 작은 값들을 고려해야 한다.

수정 코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [1]*N # dp[i] = index i까지의 최댓값
        
        for i in range(1, N):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

1. dp[i]는 nums[i]를 마지막으로 하는 최장 증가 수열의 길이이다.
2. nums[0] ~ nums[i-1] 중에서, nums[j] < nums[i]인 모든 j를 찾는다.
3. j들 중 가장 긴 수열을 고르고 nums[i]를 붙인다.

코드는 통과했다. 하지만 현재 코드는 O(n^2)의 시간 복잡도를 갖는다.

O(nlogn) 코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []

        def binary_search(target): # 이진 탐색
            left, right = 0, len(dp)-1
            while left <= right:
                mid = (left+right)//2
                if dp[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        for num in nums:
            idx = binary_search(num)
            if idx == len(dp):
                dp.append(num)
            else:
                dp[idx] = num

        return len(dp)

1. 빈 dp 배열을 생성한다.

• 실제 LIS를 저장하지 않고, 각 길이에 해당하는 최솟값의 후보들만 저장한다.

2. nums 배열을 순회한다.
3. 현재 수 num을 dp에서 이진 탐색으로 삽입할 위치 idx를 찾는다.

• dp[idx-1] < num <= dp[idx]를 만족하는 위치가 된다.

4. 찾은 위치 idx가 dp의 끝이라면 → num은 가장 긴 수열의 다음 수가 될 수 있으므로 추가

• 그렇지 않다면 → 기존 값을 num으로 덮어씌워서 더 나은 후보로 교체

5. 전체 과정이 끝나면 dp의 길이가 LIS의 길이=정답이다.

요약: nums 순회 → 이진 탐색으로 위치 찾기 → dp에 삽입 or 대체 → dp 길이 = 정답

LIS: Longest increasing Subsequence, 최장 증가 부분 수열