[4코3파] #290. Leetcode 300. Longest Increasing Subsequence

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (290일차)
[4코1파] 2023.01.13~ (282일차)
[4코3파] 2023.10.01 ~ (20일차)

Today :

2023.10.20 [290일차]

139. Word Break

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

문제 설명

정수 원소가 담긴 배열 nums가 주어질 때, 오름차순으로 증가하는 수열로 이루어진 서브시퀀스(배열)의 길이를 return함

문제 풀이 방법

brute force - dfs 로 푼다면 O(2^n) 이고,
전 인덱스에서 현재 탐색하고 있는 기준보다 큰 지점을 추가하는지 아닌지에 대한 로직이 필요하다. memoization으로 cache 한다면 O(n^2) 으로 풀이가 가능하다.
근데 또 서브 시퀀스 생성 시 sub[j]값을 nums[i]로 대체할때 배열을 binary search를 이용하면 O(logn)으로 찾을 수 있다는 것이다.
개 어려움 미쳤나

내 코드

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        LIS = [1] * len(nums)

        for i in range(len(nums),-1, -1):
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j] :
                    LIS[i] = max(LIS[i], 1+LIS[j])
        return max(LIS)

증빙

여담

이건 brute force 부터 memoization 그리고 그 뒤에 binary search 까지 천천히 다 해보면서 최적화 해야겠음