★Longest Increasing Subsequence★

LeetCode - The World's Leading Online Programming Learning Platform

★다시 풀어봐야할 문제★ (DP 기본문제에 해당, 문제 접근방식이 잘못된것 같아 해설 참고)

문제 파악 [필수 작성]

문제이해

순차적으로 초과하는 숫자로 이루어진
가장긴 리스트의 길이 리턴

제한 조건 확인

O(n^2) 이하로 풀어라

아이디어

DFS 를 이용해서 다음 노드로 진행 가능할경우에 진행
캐시를 이용해 한번 방문했던 동일한 노드는 DFS 안함

시간복잡도

자료구조

접근 방법 [필수 작성]

자유 형식

코드 구현 [필수 작성]

1차 시도

시간 초과

2^2500 이긴 하지만, 아래 조건문을 통해서 해당되지 않는 부분이 상당 수 제거될 거라고 생각했었는데, 조금만 악의적인 케이스가 들어와도 시간초과가 날 수 있다는걸 알지 못했다. 어떻게 하면 재귀코드가 충분히 불필요한 케이스를 제거하여서 시간복잡도를 완벽하게 계산하지 못해도 통과할 수 있음을 확신할 수 있는가?

if tmp_list[-1] < nums[p]:
    dfs(p + 1, tmp_list + [nums[p]])

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        #cache = set()

        def dfs(p, tmp_list):
            nonlocal max_len
            #print(tmp_list)
            if p == n:
                max_len = max(max_len, len(tmp_list))
                return
            # if tuple(tmp_list) in cache:
            #     return

            #cache.add(tuple(tmp_list))

            if len(tmp_list) == 0:
                dfs(p + 1, tmp_list + [nums[p]])
                dfs(p + 1, tmp_list)
            else:
                if tmp_list[-1] < nums[p]:
                    dfs(p + 1, tmp_list + [nums[p]])
                dfs(p + 1, tmp_list)

        dfs(0, [])

        return max_len

2차 시도

메모리 초과 → Maximum Subarray 와 같은 양상이어서 DP의 특성을 이용해 풀고있다고 생각하지 않아, 해설집 참고

[1,2,3,4,5,6] 의 nums 리스트에서

[1,2,...] 과 [2,...] 은 진행해보지 않아도
전자가 더 긴 길이를 가질 것을 알 수 있다.
이 부분을 중복제거해주어야한다.
즉, (pointer, 마지막 원소) 를 튜플형태로 키값으로 저장해주고
리스트 길이가 더 긴 경우에만 진행해준다.
예시) (3,2) = 2 이기 때문에 (3,2) 이 1 인 경우는 진행하지 않는다.

아래와 같이 조건식을 추가

        cache = defaultdict(int)

        def dfs(p, tmp_list):
            nonlocal max_len
            if p == n:
                #print(tmp_list)
                max_len = max(max_len, len(tmp_list))
                return
            if len(tmp_list) != 0:
                if cache[(tmp_list[-1],p)] >= len(tmp_list):
                    return
                else:
                    cache[(tmp_list[-1],p)] = len(tmp_list)

from collections import defaultdict
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        cache = defaultdict(int)

        def dfs(p, tmp_list):
            nonlocal max_len
            if p == n:
                #print(tmp_list)
                max_len = max(max_len, len(tmp_list))
                return
            if len(tmp_list) != 0:
                if cache[(tmp_list[-1],p)] >= len(tmp_list):
                    return
                else:
                    cache[(tmp_list[-1],p)] = len(tmp_list)
            
            if len(tmp_list) == 0:
                dfs(p + 1, tmp_list + [nums[p]])
                dfs(p + 1, tmp_list)
            else:
                if tmp_list[-1] < nums[p]:
                    dfs(p + 1, tmp_list + [nums[p]])
                dfs(p + 1, tmp_list)

        dfs(0, [])

        return max_len

3차 시도

갈아엎고, 해설 코드 아이디어만 참고 후 직접 구현

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp_list = [1 for _ in range(len(nums))]

        for r in range(1,len(dp_list)):
            for l in range(0,r): 
                if nums[l] < nums[r]:
                    dp_list[r] = max(dp_list[l]+1,dp_list[r])

        return max(dp_list)

4차 시도

이진탐색을 활용하면 O(nlogn) 으로 풀 수 있다고 하는데, 어떻게 해야할까?

→ 정답코드 봤음

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lst = []
        for num in nums:
            
            i = bisect_left(lst, num)
            
            if i == len(lst):
                lst.append(num)
            
            else:
                lst[i] = num
        
        return len(lst)

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.