[2024] Day5. 300. Longest Increasing Subsequence

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 5일 (금)
Leetcode daily problem

300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=daily-question&envId=2024-01-05

Problem

정수가 담긴 배열 nums가 주어질 때, 가장 긴 증가하는 부분 수열의 길이를 찾는 문제이다.

Solution

Dynamic programming

주어진 정수 배열에서 증가하는 부분 수열을 찾기 위해서, 원래 배열에서 원소들의 순서를 유지하고 일부 원소들을 생랴갷서 얻을 수 있는 순서대로 증가하는 부분 수열을 구해야 한다.

Dynamic programming으로 접근하기 위해서
Subproblem을 dp[i] 배열의 i 번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 길이라고 둔다. 처음은 dp[i] =1 이다. 한 원소로 이루어진 증가하는 부분 수열의 길이인 1로 둔다. 점화식으로 dp[i] = max(dp[i], dp[j]+1) 로 세워서, 그 이전에 있는 원소들 중 자기보다 작은 값을 확인해 가능한 모든 부분 수열의 길이 중 가장 작은 긴 것을 찾는다.

Code

Complexicity

시간 복잡도

이중 반복문을 사용하고 있으므로 O(n^2) 이다.

공간 복잡도

배열 nums의 길이에 비례하는 O(n) 이다.

---

개선

• 위의 코드는 배열의 길이가 길어질수록 효율성이 떨어져서, 이진탐색을 통해서 개선할 수 있다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tmp = [0]*len(nums)
        size = 0

        for num in nums:
            left, right = 0, size
            while left<right:
                mid = (left+right)//2
                if tmp[mid] < num:
                    left = mid+1
                else:
                    right = mid
            
            tmp[left] = num
            if left == size:
                size +=1
        
        return size

이 경우는 시간복잡도가 O(nlogn)이 나온다. 웨우
nums 배열과 같은 크기를 가진 0의 원소로 구성된 tmp 배열을 만든 후에,
처음 size 변수에 0을 할당한다.
배열 nums의 원소를 처음부터 탐색한다.
해당 nums의 원소를 탐색할 때마다 left, right의 값을 0과 size값으로 할당하고,
이를 이용해서 이진 탐색을 통해서 다음 배열의 원소가 큰지 작은지를 확인하고,
다음 배열이 원소가 크다면 tmp에 넣고, size를 증가시키면서 size를 업데이트한다.
이진탐색을 통해서 다음의 원소들을 체크 하기 때문에
먼저 배열을 도는 O(n) 시간복잡도와 이진탐색 O(logn)으로 총 시간복잡도는 O(nlogn)이고, 공간복잡도는 tmp에 넣는 nums의 배열의 크기 O(n) 이다.