Longest Increasing Subsequence

Longest Increasing Subsequence

문제 내용

주어진 Array에서 가장 긴 연속된 순서의 길이를 찾아라.

Array내의 Position을 수정할 순 없지만, 중간에 있는 값을 삭제 할 수는 있다.

 

접근 방법

 

Brute Force

상위와 같은 배열이 주어졌을 경우 다음과 같이 Array를 찾을 수 있다.

9보다 작은 값이 이전에 있었는가?

없었다면 dp 1을 유지한다.

2보다 더 작은 값이 있는가? 없음으로 유지한다.

5보다 작은 값이 있는가?

2가 더 작았다. 그럼 2의 dp + 1을 해준다.

3도 같은 방법으로 dp의 값을 올려준다.

7의 경우 2,5,3 중 가장 높은 dp의 값에 + 1을 해준다.

101은 4가 된다.

18도 4가 된다.

위의 방식은 Time Complexity가 $ O(n^2) $ 이 된다.

 

1D DP 유지하기

이 내용을 이해하는데 시간이 좀 결려서 글을 남기게 되었다.

위에서는 sub-sequence의 count를 dp에 유지했다면, 여기에서는 가장긴 숫자의 값을 유지하는 방식으로 접근해 보겠다.

초기 값은 무조건 1임으로 0번째 값을 넣어준다.

9가 10보다 큰가를 보면 그렇지 않다. 그럼 기존 10을 대신해서 9를 넣어 준다.

이게 괜찮은 이유는 이후에 나오는 11,12 등의 큰 값은 결국 9보다도 큰 값이 되기 때문이다.

2가 9보다 큰가? 그렇지 않다. 2로 대체해 준다.

5가 2보다 큰가? 그렇다 sub-sequence에 append해준다.

3은 5보다 큰가? 그렇지 않다. 그럼 3은 어디에 위치 해야하는가? 기존에 있던 2의 뒤에 위치하면 된다.

3이 5를 대체하게 되는데, 이것이 괜찮은 이유는

• 다음값이 5보다 작은 값이 오게 되면 길이기준으로 2,3으로 연속한 수의 길이가 가장 길기 때문에 문제없다.
• 다음값이 5보다 큰 6이 온다고 해도 길이로는 2,5,6과 ,2,3,6 둘다 같은 3의 길이기 때문에 문제 없다.

결국 3이 5를 대체하게 된다.

7은 3보다 크다. append한다.

101은 7보다 크다. append 한다.

18은 101보다 작다. 그럼으로 101이 후에 append 될수 없다. 대신 18이 101을 대체 하게 된다.

다시 한번 이것이 괜찮은 이유는

• 101보다 큰값이 18뒤에 온다고 해도, 결국 18보다 큰 값임으로 length의 길이는 변함이 없다.
• 18보다 크고 101보다 작은 값이 오게 된다면, 101이 최종일때 보다 18이 최종일때 length가 더 길게 된다 

위의 방식도 time complexity가 $ O(N^2) $ 이된다.

대신에 위의 방법은 최적화가 가능하다.

 

Binary Search 사용하기

다시 한번 위의 경우를 생각해 보자. 18이라는 값이 7뒤의 101의 자리를 교체 한다는 것은 어떻게 알았을까?

위의 방법과 같다면, "2->3->7->101" 7이후가 18이 들어갈 수 있는 직전 위치라는 것을 순차적으로 검색 했기 때문에 알 수 있다.

여기서 착안 할 수 있는 것이 있다.

• Sub Sequence의 좌측은 정렬되어 있다.

정렬되어 있다면 binary search를 이용해서 $ O(logN) $ 으로 최적화 가능하다.

2021.06.17 - [Problem Solving] - Binary Search Lower Bound와 Upper Bound

binary search를 이앵효 lower bound를 찾는 것이다. 자기 자신보다 작은 가장 직전의 point를 찾는 것이 그 목표이다.

이것을 적용하면 최종적으로 $ O(N Log N) $으로 최적화 가능하다.

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

위의 내용을 모두 적용 시킨 것이 위의 코드이다.