LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열
백준에서 문제 해결 능력을 키우면서 최장 증가 부분 수열문제를 풀게 되었다. 최장 증가 수열이란 주어진 수열의 부분 수열 중에서 숫자가 오름차순으로 정렬 되는 가장 긴 부분 수열을 의미한다. 문제를 풀면서 공부한 내용을 정리했다.
LIS 길이 구하기
몇가지 예를 들어보겠다. 주어진 수열이 1, 2, 3, 4, 5, 6, 7, 8, 9 이면 1부터 9까지 연속으로 오름차순 정렬 되어 있어서 최장 증가 부분수열의 길이는 9가 된다. 1, 2, 3, 4, 2, 5, 6, 7, 8 이면 최장 증가부분 수열은 1, 2, 3, 4, 5, 6, 7, 8이 되서 길이는 8이 된다. 조금 더 복잡한 예제를 가지고 살펴보자. 1, 5, 2, 8, 3, 4, 6 이 주어 진다면 최장 부분 증가 수열은 무엇이고 그 길이는 어떻게 될까 ?
O(n^2)으로 구하기
주어진 수열의 원소들을 순회하면서 순회하는 원소의 위치를 기준으로 했을 때 앞의 숫자들 중에서 가장 긴 LIS의 길이를 새 배열에 저장하고 순회가 끝났을 때 이 배열에서 가장 큰 값이 이 수열의 최장 증가 부분 수열이 된다.
위의 설명을 토대로 1, 5, 2, 8, 3, 4, 6 예제에 적용 해보자.
- 위치가 0일 때 [1] : 최소 1개 이상이므로 기본 값은 항상 1이다.
- 위치가 1일 때 [1, 2] : 숫자 5까지로 보면 1, 5의 증가부분 수열이 있고 2가 가장 큰 길이가 된다.
- 위치가 2일 때 [1, 2, 2] : 숫자 2까지로 보면 1, 2의 증가부분 수열이 있고 이전까지와 동일하게 2가 가장 큰 길이가 된다.
- 위치가 3일 때 [1, 2, 2, 3] : 숫자 8까지로 보면 1, 5, 8 또는 1, 2, 8이라는 증가부분 수열이 추가 되서 이전과 다르게 3이 가장 큰 길이가 된다.
- 위치가 4일 때 [1, 2, 2, 3, 3] : 숫자 3까지로 보면 1, 2, 3이라는 증가부분 수열이 추가 되었으나 이전까지와 동일하게 가장 큰 길이는 3이다.
- 위치가 5일 때 [1, 2, 2, 3, 3, 4] : 숫자 4까지로 보면 1, 2, 3, 4라는 증가부분 수열이 추가되어 이전과 다르게 가장 큰 길이는 4가 된다.
- 위치가 6일 때 [1, 2, 2, 3, 3, 4, 5] : 숫자 6까지로 보면 1, 2, 3, 4, 6이라는 증가부분 수열이 추가되어 이전과 다르게 가장 큰 길이는 5가 된다.
자바스크립트 코드로 다음과 같이 구현 할 수 있다.
const nums = [1, 5, 2, 8, 3, 4, 6]
const lis = new Array(7).fill(1);
for (let i = 0; i < nums.length; i ++) {
for (let j = 0; j < i; j ++) {
if (nums[i] > nums[j]) {
lis[i] = Math.max(lis[j] + 1, lis[i]);
}
}
}
console.log(lis) // [1, 2, 2, 3, 3, 4, 5]
console.log(Math.max(...lis)); // 5
1, 5, 2, 8, 3, 4, 6의 최장 증가 부분 수열은 1, 2, 3, 4, 6 이고 길이는 5가 된다. 이 알고리즘을 그대로 사용해서 BOJ 11053 - 가장 긴 증가하는 부분 수열 실버2 문제를 해결 할 수 있다.
O(nlogn)으로 구하기
이 알고리즘은 위의 알고리즘을 개량한 형태로 나무위키를 보고 이해한 내용을 정리 했다. 1줄로 요약하면 순회하는 원소까지의 숫자로 끝이 가장 작은 수로 끝나면서 가장 긴 증가 부분 수열을 만들면 된다. 동일하게 1, 5, 2, 8, 3, 4, 6 예제를 가지고 살펴보겠다.
i = 0 일 때 첫 번째 원소를 추가한다. 새 배열은 X라고 하겠다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] |
i = 1 일 때 5는 앞에서의 부분 수열의 맨 뒤인 1보다 크기 때문에 뒤에 추가한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 5] |
i = 2 일 때 2는 5를 대신한다면 1, 5보다는 1, 2가 가장 긴 증가부분 수열을 만들기 위해 앞으로 뒤에 붙일 수 있는 숫자가 더 많으니까 5의 인덱스인 1을 구해서 X의 1번째 값 5를 2로 갱신한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 5] | [1, 2] |
i = 3 일 때 8은 앞에서의 부분 수열의 맨 뒤인 2보다 크기 때문에 뒤에 추가한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 5] | [1, 2] | [1, 2, 8] |
i = 4 일 때 3은 8을 대신한다면 1, 2, 8보다는 1, 2, 3이 가장 긴 증가부분 수열을 만들기 위해 앞으로 뒤에 붙일 수 있는 숫자가 더 많으니까 8의 인덱스인 2를 구해서 X의 2번째 값 8을 3으로 갱신한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 5] | [1, 2] | [1, 2, 8] | [1, 2, 3] |
i = 5 일 때 4는 앞에서의 부분 수열의 맨 뒤인 3보다 크기 때문에 뒤에 추가한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 5] | [1, 2] | [1, 2, 8] | [1, 2, 3] | [1, 2, 3, 4] |
i = 6 일 때 6은 앞에서의 부분 수열의 맨 뒤인 4보다 크기 때문에 뒤에 추가한다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 1 | 5 | 2 | 8 | 3 | 4 | 6 |
| X | [1] | [1, 2] | [1, 2, 8] | [1, 2, 3] | [1, 2, 3, 4] | [1, 2, 3, 4, 6] |
이렇게 주어진 수열을 순회하면서 최대한 작은 숫자들로 증가 부분 수열을 만들면 그 길이가 최장증가 부분 수열의 길이가 된다. 여기서 주의 할 점이 이 예제만 보고 위 알고리즘으로 만들어진 배열 X가 최장 증가 부분 수열을 만든다고 생각 할 수 있다. 하지만 배열 X는 어디까지나 LIS의 길이를 구하는 배열이다.
이 부분은 수열이 2, 3, 4, 1, 5, 2, 7, 8, 3, 4, 6인 예제를 가지고 확인 해보면 알 수 있다.
- 배열 X는 1, 2, 3, 4, 6, 8 이 되고 최장증가 부분 수열은 2, 3, 4, 5, 7, 8 이 된다.
LIS 수열 구하기
위의 O(nlogn) 알고리즘으로 구하는 배열 X는 최장증가부분 수열은 아니지만 이 알고리즘을 구현하는 과정에서 원본 인덱스를 저장하는 또 다른 배열을 만들어서 LIS 수열을 구할 수 있다.
먼저 배열 X를 만들기 위한 위치 인덱스를 반환하는 lowerBound 함수를 이진탐색을 기반으로 구현한다. lowerBound는 정수 k와 정수 배열이 주어지면 k이상인 수가 처음으로 등장하는 위치를 반환 한다. 위에 알고리즘 설명 글에서 “x(n)의 인덱스인 n을 구해서”라는 설명에 해당 하는 부분이다.
const lowerBound = (value, list) => {
let left = 0;
let right = list.length
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (list[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
lowerBound 함수를 구현하고 배열 X를 lis라는 이름으로 선언하고 0번째에는 원본 배열의 0번째 값을 추가했다. 그리고 1번째 값부터 순회하면서 어느 위치에 들어갈 수 있는지를 lowerBound 함수로 구한다. 하나하나 살펴본 예시와 같이 순회하는 값이 가장 커서, 즉 반환된 인덱스와 lis 배열의 길이가 같다면 뒤에 추가를 하고 그렇지 않으면 갱신을 한다. 이때 또 다른 배열에는 반환된 인덱스 + 1을 저장해서 순회하는 값까지의 최장 증가 부분 수열의 길이를 indexes에 저장한다.
const arr = [2, 3, 4, 1, 5, 2, 7, 8, 3, 4, 6];
const indexes = [1];
const lis = [arr[0]];
for (let i = 1; i < arr.length; i++) {
const index = lowerBound(arr[i], lis);
if (index === lis.length) lis.push(arr[i]);
else lis[index] = arr[i];
indexes.push(index + 1);
}
console.log(indexes) // [1, 2, 3, 1, 4, 2, 5, 6, 3, 4, 5]
console.log(lis) // [1, 2, 3, 4, 6, 8]
최장 증가 부분 수열을 구하기 위해서 indexes을 뒤에서부터 가장 큰 길이 부터 1까지 처음 나오는 순간의 인덱스를 가지고 원본 값을 찾아서 저장하고 뒤집는다. lis의 길이는 6이니까 원소의 길이인 10부터 거꾸로 순회하는데 6부터 1까지 처음 나올 때의 인덱스를 가지고 원본 배열에서 값을 구한다. 6이 처음 나오는 인덱스는 7이므로 answer에 처음 추가되는 값은 원본 배열의 7번째 원소인 8이 추가된다. 다음에는 5가 처음 나오는 인덱스가 6이므로 원본 배열의 6번째 원소인 7을 추가한다. 이렇게 반복하면 [8, 7, 5, 4, 3, 2] 배열이 완성된다. 뒤집으면 최장증가 부분 수열이다.
const answer = [];
let j = indexes.length - 1;
while (answer.length < lis.length) {
if (indexes[j] === lis.length - answer.length) {
answer.push(arr[j]);
}
j--;
}
console.log(answer.reverse().join(' ')) // 2 3 4 5 7 8
이렇게 구현한 O(nlogn) 알고리즘으로는 BOJ 14003 - 가장 긴 증가하는 부분 수열 5 플래티넘5 문제를 해결 할 수 있다.
마무리
이 글은 뒤늦게 PS 공부를 시작한 필자가 LIS (Longest Increasing Subsequence)에 대한 기억이 희미해질 때 쉽게 이해할 수 있도록 작성한 글이다. 관심이 있으신 분들은 이 글의 코드를 참고하여 응용해보시기 바란다.