[Leetcode]300. Longest Increasing Subsequence(x)

1. problem : 

https://leetcode.com/problems/longest-increasing-subsequence/description/ 

 

 

2. solution 1 : 

import java.util.Arrays;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; 
        Arrays.fill(dp, 1); // 각 위치에서 최소 길이는 1
        for (int i =1;i < n;i++) {
            for (int j = 0;j < i;j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        int maxLength = 0;
        for (int length:dp) {
            maxLength = Math.max(length,maxLength);
        }
        return maxLength;
    }
}

이 문제를 푸는데 실패했다. gpt 4o한테 물어봤다. 그중 첫 번째 풀이가 DP이다. 우선 dp라는 배열을 만들고, 1로 채운다. 

그런 다음, nums [i] > nums [j]를 만족한다면, 나는 그전에 갱신되었던 dp라는 배열에서 새로 시작할 건지 아니면 기존에 있던 값을 이을 것인지를 선택하는,  Math.max() method를 이용한다. 저번에 비슷한 문제 풀었는데, 왜 생각하지 못했을까? 

 

 

3. solution 2 :

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        # tails 배열을 생성
        tails = []

        for num in nums:
            # tails 배열에서 num이 들어갈 위치를 찾는다
            pos = bisect.bisect_left(tails, num)

            # 만약 pos가 tails의 길이와 같다면 num을 추가한다
            if pos == len(tails):
                tails.append(num)
            # 그렇지 않다면 tails[pos]를 num으로 교체한다
            else:
                tails[pos] = num

        return len(tails)

이 알고리즘은 binary search를 이용하여 푸는 방법이다. 시간복잡도는 O(n logn)이 나온다. 아직 이 풀이가 완벽히 이해되지는 않는다. pos라는 변수에 bisect.bisect_left()라는 method를 이용해, tails에 num이 어디에 들어갈지 인덱스를 저장한다. 그 인덱스가 끝이면 추가하고, 아니면 기존에 들어가야 하는 자리의 원소랑 바꿔치기한다. 그 이유는 크다면 그냥 길이가 1개 증가되었다는 말이고, 작다면 길이가 증가되면 안 된다. 따라서, 길이는 변화시키지 않고, 바꿔치기로 끝낸다.