LIS
최장부분증가수열은 특정 수열에 대해서 각 원소가 점점 증가하는 조건을 만족하는 부분수열 중에 가장 긴 수열을 의미한다.
위키백과
영어로는 Longest Increasing Subsequence 줄여서 LIS.
개발을 나무위키로 배웠더니...
문제를 보자마자 어떻게 풀었는지는 잊어버렸지만 예전에도 이런 문제를 푼 기억은 났다. DP를 이용했다는 것과 뭔가 장황한 설명이 있던 위키문서가 있어서 참고했다는 기억은 나는데, 어떻게 접근했는가는 잊어버려서 문서를 보고 따라해보려고 했다.
설명을 대충 읽으면서 구현하고 나서 보니 시간초과. 내가 구현한 알고리즘을 차분히 들여다보니 dp에 활용하려고 값을 저장 해 놓은 배열을 제대로 순회하도록 만들어놓질 못해서 생긴 문제였다.
위키꺼라
생각해보니 맨 처음 파이썬으로 LIS를 찾는 알고리즘을 구현하려 했을 때도 저 설명이 알고리즘을 구현하는데 큰 도움이 되진 않았다.
DP
결국 토론장에 파이썬으로 올라온 구현 중 하나를 Typescript로 옮겼다.
효율적인 알고리즘을 배우고자 한 것보다는 생각한 것, 다른 사람이 비슷하게 만든 것을 보고 내가 코드로 옮길 수 있나 확인 & 연습 하기 위해서 아는 지식을 총 동원해 파이썬 코드를 타입스크립트로 옮겨보았다
Typescript 코드
function lengthOfLIS(nums: number[]): number {
if (!nums.length) return 0;
const dp: number[] = Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
return dp.reduce((a, c) => a > c ? a : c, 0};
}변형
답안이 통과되는 것을 확인 한 뒤 몇 번에 걸쳐서 튜닝을 했는데, 맨 처음 제출이 776ms로 다른 제출에 비해 엄청 느렸던 것은 반환 값을 array.reduce를 이용해 찾은게 문제였다고 생각했다.
이러면 저장된 값 중 최대 값을 확인 하기 위해 배열을 한 번 더 순회하니까 결과적으로 O(n3)일까?
테스트 케이스 중에 길이가 1500이 넘는 부분수열도 있던데 시간초과가 안 난게 용하다.
차라리 값이 저장될 때마다 지금 저장된 값이 최대 값인가 확인하고 저장하는게 낫겠다 싶어서 변수를 만들었다. 그게 284ms 답안.
let res: number = 1;
...
dp[i] = dp[i] > dp[j]+1 ? dp[i] : dp[j] + 1;
res = dp[i] > res ? dp[i] : res;
...
return res;이후에 파이썬에선 max()를 쓰길래 js에도 비슷한게 있나 봤더니 Math.max()가 있었다. Math.max()가 어떻게 구현되어있는진 모르겠지만, 이후 제출들이 284ms보다 빠른 걸 보면 삼항연산자로 확인하는 것보다 Math.max()를 쓰는 것이 빠른 모양이다.
결과
function lengthOfLIS(nums: number[]): number {
if (!nums.length) return 0;
const dp: number[] = Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
return Math.max(...dp);
}DP를 활용하여 효율을 높인 결과 시간초과는 면했지만 결국 시간 복잡도는 O(n2)이 되어있었다.
Binary Search
사실 이게 오늘 이 글을 쓴 이유다.
지난 주에 값을 비교하고 저장하는 알고리즘을 구현하라는 문제가 있어서 오랜만에 이진탐색트리를 구현해봤는데, 이번에도 또 이진탐색을 하라고? 싶어서 걸렀다가 설명을 보니 이쪽이 이해가 쉬워서 이진탐색으로도 풀어보았다.
Typescript 코드
function lengthOfLIS(nums: number[]): number {
const tails: number[] = [];
let size: number = 0;
nums.forEach((elem) => {
let [s, e] = [0, size];
while (s != e) {
let p = ((s + e) / 2) | 0;
if (tails[p] < elem) {
s = p + 1;
} else {
e = p;
}
}
if (tails[s] === undefined) {
tails.push(elem);
size++
} else {
tails[s] = elem;
}
});
return size;
}
코드 해설
원문이 영어라 읽기 싫은 사람들을 위해 최대한 단순하게 설명하자면,
- 주어진 수열에 대해 길이가 i인 모든 증가부분수열을 찾고
- 1에서 찾은 수열 중에 마지막 원소가 가장 작은 수열을 찾고
- 2에서 찾은 수열의 마지막 원소를 i-1번 인덱스에 저장하는 배열을 만든 뒤
- i가 n이 될 때 까지 i를 늘려가며 1, 2, 3번을 반복한다.
1번과 2번을 어떻게 구현할 지 막막한데, 3번에서 만드는 배열이 부분증가수열이기 때문에 우리는 각 원소들이 배열의 어디에 저장될지만 찾아주면 된다고 한다. 그리고 3번 배열을 변경 해야하는 경우의 수는 겨우 2가지 라고 한다.
a. 새 원소가 배열에 저장된 그 어떤 수보다 크면, 배열의 맨 마지막에 추가해준다.
b. 새 원소가 배열의 i-1번째 수보다는 크지만, i번째 수보다는 작다면, 배열의 i번째 원소를 변경 해준다.
이걸 읽고 든 생각이 a만 있어도 최장길이를 찾을 수 있는 것 아닌가 싶어 b 부분을 지워봤더니 중간부터 시작되는 이전보다 더 긴 부분수열에 대응을 못한다.
이제 원리는 알았으니 각 원소들에 대해 이진탐색을 진행하면 된다.
위에 적은 forEach이하 while문이 이진탐색을 통해 새 원소의 자리를 찾는 부분이고, if else문이 업데이트 할 필요가 있는지 확인하는 부분이다.
이진탐색에 대해서는 그림과 함께 더 자세한 설명을 해주신 분이 있으리라 믿고 생략한다. 이미 글이 너무 길다.
변형
아무리 생각해도 a 부분은 tails[-1]로 접근해 확인하면 O(1) 이라 이득 아닌가 싶어 a 부분과 b 부분을 나눠보았다.
function lengthOfLIS(nums: number[]): number {
const tails: number[] = [nums.shift()];
let size: number = 1;
nums.forEach((elem) => {
if (elem > tails.at(-1)) {
tails.push(elem);
size++;
} else {
let [s, e] = [0, size];
while (s != e) {
let p = ((s + e) / 2) | 0;
if (tails[p] < elem) {
s = p + 1;
} else {
e = p;
}
}
tails[s] = elem;
}
});
return size;
}O(log n)이 O(1)으로 줄어든 부분이 생겼지만 일부여서 그런지 성능에 엄청난 변화가 생기진 않았다.
결론
처음 코드의 시간복잡도는 각 원소를 순차적으로 한 번 더 확인 하기 때문에 O(n2)고, 두 번째 코드의 시간복잡도는 각 원소를 이진탐색 하기 때문에 O(n log n)인데 테스트 수치 상으로는 2배 정도 차이가 났다.
토론장에 있는 내용으로는 파이썬을 이용하면 48ms가 걸린다는걸 보면 이런 알고리즘을 해결하는데 있어 ts랑 py랑 2배 가량의 성능차이가 나는 모양이다.
하지만 어차피 java로 짜면 2ms 라고 하고, cpp로 하면 0ms 나올 것 같다.
O(n log n) 해설을 쓰고 나니 나무위키 설명이 이해가 된다.
