소개
최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다.
어떤 수열이 있다 하자. 그 수열 중에서 몇 가지 숫자를 제거해서 만든 수열을 부분 수열(Subsequence)이라고 한다.
어떤 수열의 부분 수열들 중에는 오름차순으로 정렬되어 있는, 갈수록 숫자가 증가하는 부분 수열 또한 존재할 것이다. 이러한 특징을 갖는 부분 수열들 중에서, 길이가 가장 긴 부분 수열을 구하는 문제가 최장 증가 부분 수열(LIS) 문제이다.
수열 3, 4, 1, 2, 7, 5 ,8 을 예로 들어 설명하겠다.
이 수열로 만든 부분 수열에는 아래와 같은 것들이 있다.
- 3, 1, 7, 5
- 1, 2, 8
- 3, 4, 5, 8
이들 중에서 두 번째, 세 번째 부분 수열이 증가하는 부분 수열이다. (오름차순으로 정렬되어 있는 것을 볼 수 있다.)
또한, 이 수열이 부분 수열들 중에서 최장 증가 부분 수열은 ‘3, 4, 5, 8’이다.
하지만 좀 더 생각해 보면, ‘1, 2, 5, 8’이나 ‘1, 2, 7, 8’ 등도 최장 증가 부분 수열이 될 수 있다는 것을 알 수 있다. 이처럼, 어떤 수열의 최장 증가 부분 수열은 여러 개가 존재할 수도 있다.
알고리즘
LIS의 길이를 구하는 문제를 해결할 수 있는 알고리즘에 대해 알아보자.
새로운 배열 DP를 정의하자. DP[i]의 정의는 다음과 같다.
DP[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이
A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다.
따라서 A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.
수열 A = 1 2 1 3 2 5 을 예로 들어 알고리즘을 살펴보자.
(알고리즘의 규칙성을 위해 i = 0일 때를 추가하자. i = 0일 때 A[i] = 0, DP[i] = 0이다.)
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 |
i = 1일 때를 살펴보자.
A[1] = 1이다. 1은 A[0] = 0 뒤에 붙을 수 있다. 따라서 DP[1] = DP[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 |
i = 2일 때를 살펴보자.
A[2] = 2이다. 2는 A[0] = 0, A[1] = 1 뒤에 붙을 수 있다. 이 때 DP[0] = 0, DP[1] = 1에서 DP[1]이 가장 크다. 이 말은 A[1] = 1을 가장 마지막 값으로 가지는 증가부분수열의 길이가 가장 길다는 뜻이다. A[2]가 가장 긴 증가부분수열 뒤에 붙는 것이 더 긴 증가부분수열을 만들 수 있다. 따라서 DP[2] = DP[1] + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 | 2 |
i = 3일 때를 살펴보자.
A[3] = 1이다. 1은 A[0] = 0 뒤에 붙을 수 있다. 따라서 DP[3] = DP[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 | 2 | 1 |
i = 4일 때를 살펴보자.
A[4] = 3이다. 3은 A[0] = 0, A[1] = 1, A[2] = 2, A[3] = 1 뒤에 붙을 수 있다. 이 때 DP[0] = 0, DP[1] = 1, DP[2] = 2, DP[3] = 1에서 DP[2]가 가장 크다. 따라서 DP[4] = DP[2] + 1 = 3이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 | 2 | 1 | 3 |
i = 5일 때를 살펴보자.
A[5] = 2이다. 2는 A[0] = 0, A[1] = 1, A[3] = 1 뒤에 붙을 수 있다. 이 때 DP[0] = 0, DP[1] = 1, DP[3] = 1에서 DP[1]이 가장 크다. 따라서 DP[5] = DP[1] + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 | 2 | 1 | 3 | 2 |
i = 6일 때를 살펴보자.
A[6] = 5이다. 5는 A[0] = 0, A[1] = 1, A[2] = 2, A[3] = 1, A[4] = 3, A[5] = 2 뒤에 붙을 수 있다. 이 때 DP[0] = 0, DP[1] = 1, DP[2] = 2, DP[3] = 1, DP[4] = 3, DP[5] = 2 에서 DP[4]가 가장 크다. 따라서 DP[6] = DP[4] + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 2 | 1 | 3 | 2 | 5 |
| DP | 0 | 1 | 2 | 1 | 3 | 2 | 4 |
이렇게 해서 배열 DP를 다 완성했다. DP의 값들 중 가장 큰 값(DP[6] = 4)이 수열 A = 1 2 1 3 2 5의 LIS의 길이다.
이 알고리즘은 N개의 수들에 대해 자기 자신 전의 모든 수를 다 훑어봐야 하므로 O(N^2)의 시간복잡도를 가지는 알고리즘이 된다.
문제 소개
백준 #11053. 가장 긴 증가하는 부분 수열 문제를 풀어 보자. 위에서 소개한 알고리즘을 그대로 적용하면 풀 수 있는, 대표적인 LIS 문제이다.
백준 #11053. 가장 긴 증가하는 부분 수열
아래 링크는 내가 위 문제를 풀고 나서 정리와 정답 코드를 기록해 둔 Velog 링크이다.
https://velog.io/@chnh506/백준-11053-가장-긴-증가하는-부분-수열
