최장 증가 부분 수열 알고리즘
📌최장 증가 부분 수열이란?
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.
예를 들어 다음 수열이 있다고 가정합시다.
[3, 5, 7, 9, 2, 1, 4, 8]
위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있습니다. (여기서 한 가지 헷갈렸던 점은, 꼭 공차가 존재하지 않아도 부분수열로 본다는 점입니다. 수열 [1, 3, 5, 7]같이 공차가 존재하지 않더라도 부분수열입니다.)
[3, 7, 9, 1, 4, 8] (5, 2제거)
[3, 5, 7, 8] (9, 1, 4제거)
[1, 4, 8] (3, 5, 7, 9, 2제거)
... 등등
이들 중 두 번째와 세 번째 수열은 오름차순으로 정렬되어 있습니다. 이를 증가 부분 수열이라고 합니다.
그리고, 이런 증가 부분 수열 중에서 가장 긴 수열을 최장 증가 부분 수열(LIS) 라고 합니다. 예제 수열에서 LIS는 [3, 5, 7, 8] 입니다.
📌LIS를 구하는 방법
🔍 1. DP 이용하기 : O(N^2)
D[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다. 부분수열 A의 i번째 요소가 어떤 증가 부분 수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이어야 합니다. 따라서 A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이는 A[i]가 추가될 수 있는 증가 부분 수열 중 가장 긴 수열의 길이에 1을 더한 값이 됩니다.
for (let i = 0; i < n; i++) {
D[i] = 1;
for (let j = 0; j < n; j++) {
D[i] = Math.max(D[i], D[j] + 1);
}
}이 알고리즘은 n개의 수들에 대해 모든 수들을 다 훑어봐야 하므로 O(N^2)의 시간복잡도를 가집니다. 만약 n이 백만 개 정도만 되어도 실행시간이 10초 이상 소요됩니다.
- DP로 LIS를 풀 수 있는 문제: 백준 2565번 - 전깃줄
🔍 2. 이분탐색 이용하기 : O(NlogN)
1번 방법의 시간복잡도를 개선하기 위해 이분탐색을 활용할 수 있습니다. 1번은 n개의 수가 모든 수를 훑어봤지만 이분탐색을 활용하면 모든 수를 탐색하지 않고 해결할 수 있습니다.
이분탐색으로 타겟수가 배열안 mid에 해당하는 수보다 크다면 start point를 mid + 1로 옮기고, 작거나 같다면 end point를 mid - 1로 옮깁니다. 이런 작업을 반복해 타겟수가 배열 안에 어디에 넣을지 결정할 수 있습니다.
function binary_search(arr, val) {
start = 0;
end = arr.length - 1;
while (start <= end) {
mid = (start + end) / 2;
if (arr[mid] > val) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
num_arr = [3, 7, 9, 1, 4, 8];
D = [];
for (const num of num_arr) {
if (D.length === 0 || D[D.length - 1] < num) {
D.push(num);
} else {
D[binary_search(D, num)] = num
}
}
- 이분탐색으로 LIS를 풀 수 있는 문제:
- 백준 2352번 - 반도체 설계
- 백준 12015번 - 가장 긴 증가 부분 수열2
📎 Reference
