[LeetCode] 300. Longest Increasing Subsequence (C++)

문제

 

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

Longest Increasing Subsequence - LeetCode

 

풀이

 

난이도: Medium 

 

대표적인 DP문제로 최대 증가 부분 수열(LIS) 문제라고 한다.

O(n^2)의 풀이와 O(n log(n))의 풀이가 있는데 두 개 다 소개하도록 하겠다.

 

 

1. O(n^2)  풀이

 

가장 간단한 풀이로 배열의 뒤에서부터 해당 원소가 증가수열에 포함된다면 얼마나 긴 증가수열을 만들 수 있는지 계산하면 된다.

자세한 풀이는 이전에 해설한 동일한 문제로 대체한다.

 

[알고스팟] LIS - Longest Increasing Sequence/ 최대 증가 부분 수열 (C++)

[알고스팟] LIS - Longest Increasing Sequence/ 최대 증가 부분 수열 (C++)

 

 

 

 

2.  O(n log(n))  풀이

 

c++의 lower_bound 함수를 이용하여 해결한다.

lower_bound(iterater first, iterater last, const T& key)는 오름차순으로 정렬된 배열의 [first, end)의 범위에서 key를 이진 탐색으로 찾는다.

만약 key값이 배열에 없다면 key다 큰 값 중에 가장 작은 값의 위치를 iterater로 반환한다.

따라서 배열의 모든 값이 key보다 작다면 arr.end를 반환하게 된다.

 

이제 새로운 배열(arr)을 이용해서 LIS를 찾아보자.

 

 

 

비어있는 배열 arr에서 nums[idx]를 0에서부터 순서대로 lower_bound search를 한다.

만약 배열의 모든 값이 nums[idx] 작다면 lower_bound는 arr.end를 반환한다. (비어있는 경우도 동일)

이때는 arr의 뒤에 nums[idx]를 push 해준다.

 

lower_bound가 반환한 값이 arr.end가 아니라면 반환 값은 key보다 큰 값 중에 가장 작은 값의 위치일 것이다.

이 위치에는 nums[idx]를 덮어씌워 주자.

 

이와 같은 과정을 반복하면 arr는 LIS가 된다.

그 이유는 arr는 항상 오름차순으로 유지되기 때문이다.

nums[idx]가 arr의 어떤 원소보다 크다면 가장 뒤로 push된다. (이 경우에만 arr의 len이 증가)

nums[idx]가 arr의 원소로 대체하(덮어씌우)는 경우는 nums[idx]가 arr의 특정값과 같거나 nums[idx]보다 큰 값이 있을 때이다.

이때 num[idx]는 자신보다 큰 값 중 가장 작은 값과 대체된다. (같은 값이면 같은 값과 대체되므로 변화 x)

따라서 arr의 길이는 변화가 없지만, 원소가 더 작은 값으로 대체되었으므로 더 큰 값을 원소로 가지는 부분 배열보다는 항상 이득이다.

 

결과적으로 모든 nums[idx]값을 순서대로 진행시키면 arr에는 LIS가 획득되고 이 길이가 LIS의 길이이다.

lower_bound는 이진 탐색으로 O(log n)의 복잡도를 가지므로, 총 시간 복잡도는 O(n log(n))이 된다.

 

[10,9,2,5,3,7,101,18]

 

10 -> [10]          push 10

9 -> [9]             10 replaced to 9

2 -> [2]             9 replaced to 2

5 -> [2,5]           push 5

3 -> [2,3]           5 replaced to 3

7 -> [2,3,7]         push 7

101 -> [2,3,7,101] psuh 101

18 -> [2,3,7,18]   101 replaced to 18