300. Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

윽 어려웠다!

 

어레이가 주어졌을 때 증가하는 수열로만 이루어지면서 가장 긴 subseq를 찾는 문제다.

 

처음엔 정렬하고나서 인덱스로 뭐 어떻게 해보면 되지 않을까 생각해봤는데, 

 

정렬하고 나서도 결국 증가하는 인덱스로만 이루어진 배열을 찾아야되서 결국 같은 문제로 회귀...

 

힌트를 얻으니

 

가장 브론즈식으로 접근하면 2^n으로 접근 가능하다.

 

이전 기준점(prev)이 있을 때, 해당 기준점 보다 큰 지금 지점(cur)을 추가할지/말지 결정하는 식으로 재귀 함수를 짜면 됨...

 

다만 이렇게 했을 때 무조건 문제에서 제시하는 기준인 n^2를 만족 하지 못한다.

 

여기서 memoization을 적절히 활용(prev, cur)를 기준으로 메모를 하면 n^2까지 최적화가 가능하다.

 

나는 dynamic programming으로 접근해보았다.

 

해설에 나오는 접근법과 거의 동일한데, 

 

아래 와 같은 문구를 기억하고 싶다.

 

This method relies on the fact that the longest increasing subsequence possible upto the i^{th}ith index in a given array is independent of the elements coming later on in the array. 

 

어쨌든 풀이는 아래와 같고, 65% 정도의 성능이 나왔다.

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

        dp = [0]*len(nums)
        
        for i, n in enumerate(nums):
            max_len = 1 
            for j in range(i-1, -1, -1):
                if nums[j] >= n:
                    continue
                max_len = max(max_len, dp[j]+1)
            
            dp[i] = max_len
            
        return max(dp)

 

경험상 1차원 어레이를 이용한 dp에선

품앗이 혹은 도둑질

도둑질 ; 현재 지점으로 (이전)다른 지점을 스캔하면서 가져와보기

품앗이 ; 현재 지점으로 부터 (다음)다른 지점으로 값을 나눠줘 보는 식

두 가지 정도 유형으로 분류가 가능한듯 싶다.