300. Longest Increasing Subsequence
풀이1. DP
숫자들을 순회하면서, 해당값까지 가능한 LIS길이를 dp어레이에 저장한다.
해당 인덱스 이전값을 순회하면서 가장 긴 값을 찾아 1 증가시켜준다.
나보다 작은값이 없어서 LIS갱신이 불가능한 경우에도 "나 자신"으로 이루어진 길이1짜리 LIS가 존재하므로 max초기값 0에 1을 더한 1로 dp에 저장하게 된다.
정답으로 반환할 가장 긴 LIS를 갱신하며 진행한다.
Time, Space
이중반복으로 time O(N^2)가 소요되고, space O(N)이 소요된다.
var lengthOfLIS = function(nums) {
const dp = Array(nums.length).fill(1);
let ans = 1;
for(let i=1; i<nums.length; i++){
let max=0;
for(let j=i-1; j>=0; j--){
if(nums[j] < nums[i]) max = Math.max(max, dp[j]);
}
dp[i] = max+1;
ans = Math.max(ans, dp[i]);
}
return ans;
};
풀이 2. Binary Search+DP
위 풀이에서, 앞 요소들을 순회하는 반복문을 개선하기 위한 방식이다.
dp와 count를 사용하지않고 sub을 저장해가면서, 이 sub를 이진탐색하여 길이를 구할 수 있다.
(참고로, 문제풀이에 사용되는 sub는 LIS가 아니다. 정확히 말하면, LIS의 길이를 측정하기 위해 사용되는 어레이이다. 밑에 풀이를 보면 이해할 수 있다.)
sub에 수를 추가할 수 있는 조건은 딱 한가지이다. sub의 가장 큰수, 즉 가장 끝에있는 수보다 큰 수가 나타났을때에만 추가할 수 있다.
다음 세가지 경우로 나눌 수 있다.
1. sub의 가장 큰 수보다 큰 수가 나타났을 때
sub끝에 추가한다.
2. sub의 가장 큰 수와 같은 수가 나타났을 때
그냥 넘어간다.
3. sub의 가장 큰 수보다 작은 수가 나타났을 때
binary search의 lower bound 방식을 통해, sub에서 해당 수가 들어갈 자리를 찾아 그 자리에 덮어씌워 교체시킨다.
정답은 sub의 길이가 된다.
이해하기 위해, 예시를 보면 다음과 같다.
nums = [1,2,7,8,3,4,5,9,0]
value -> sub
1 -> [1]
2 -> [1,2]
7 -> [1,2,7]
8 -> [1,2,7,8]
3 -> [1,2,3,8]
// 7을 3으로 교체한다.
// 여기서 sub이 LIS가 아닌 의미가 나타난다.
// [1,2,3,8]은 순서가 안맞기 때문에 LIS가 아니다.
// 하지만 [1,2,7,8]은 LIS가 맞는데, 우리는 [1,2,7,8]의 길이를 그대로 유지하면서
// [1,2,7]대신 [1,2,3]이라는 새로운 sequence를 저장하게 된 셈이다.
// 왜이렇게 하냐면 [1,2,7]보다 [1,2,3]이 더 작은수로 끝나기 때문에 더 긴 시퀀스를 만들 기회가 있기에 3으로 교체해준다.
// 8은 3보다 크고 8보다 작은수가 나타난다면 사라지게 될 것을 알수있다.
4 -> [1,2,3,4]
// 8을 4으로 교체한다.
// 역시 [1,2,7,8] 길이를 그대로 유지하면서 새로운 4라는 숫자가 포함된 시퀀스를 저장하게 되었다.
5 -> [1,2,3,4,5]
// 5를 추가한다. 길이를 갱신할 수 있는 것은 sub의 가장 큰수보다 클 때뿐이다.
9 -> [1,2,3,4,5,9]
0 -> [0,2,3,4,5,9]
// 1을 0으로 교체한다.Time, Space
이런식으로 진행하면 time O(NlogN)으로 수행할 수 있다. sub은 최대길이가 N이 될수있으므로 space O(N)이다.
var lengthOfLIS = function(nums) {
if(nums.length===1) return 1;
const sub=[nums[0]];
for(let i=1; i<nums.length; i++){
if(sub[sub.length-1] === nums[i]) continue;
if(sub[sub.length-1] < nums[i]){
sub.push(nums[i]);
continue;
}
let l=0;
let r=sub.length-1;
while(l<r){
const m=(l+r)/2<<0;
if(sub[m] < nums[i]) l=m+1;
else r=m;
}
sub[l]=nums[i];
}
return sub.length;
};
🏃🏻♀️💨