LIS 길이 구하기
https://www.acmicpc.net/problem/11053
LIS 알고리즘은 기본적으로 DP를 이용하며, 다음과 같이 점화식을 정의할 수 있다.
dp[i] = 자신보다 크기가 작은 0~(i-1)번째 원소 중에서 dp의 최댓값 + 1
이게 무슨 말인지는 예제를 통해 시뮬레이션 해보면 알 수 있다!
i = 0
{10, 20, 10, 30, 20, 50}
수열의 0번째 원소 앞에는 다른 원소가 없으므로, dp[0]에 자신의 길이인 1을 저장한다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp | 1 | 0 | 0 | 0 | 0 | 0 |
i = 1
{10, 20, 10, 30, 20, 50}
arr[1] 이전에 arr[1] 보다 작은 원소는 arr[0]이다. 이 원소의 dp 값에 1을 더해서 dp[1]에 저장한다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp | 1 | 2 | 0 | 0 | 0 | 0 |
i = 2
{10, 20, 10, 30, 20, 50}
arr[2] 앞에 자신보다 작은 원소는 없으므로, dp[2]에 1을 저장한다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp | 1 | 2 | 1 | 0 | 0 | 0 |
i = 3
{10, 20, 10, 30, 20, 50}
arr[3] 앞에 자신보다 작은 원소 중에서, dp 테이블에 저장된 최댓값은 2이므로, +1 해서 dp[3]에 3을 저장한다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp | 1 | 2 | 1 | 3 | 0 | 0 |
...
결과적으로 다음과 같은 dp 테이블이 완성되며, 이 중에서 최댓값인 4가 LIS의 길이가 된다.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| dp | 1 | 2 | 1 | 3 | 2 | 4 |
O(N^2) 풀이
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1001;
int arr[MAX];
int dp[MAX];
int ans = 0;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i = 0; i < N; i++){
cin >> arr[i];
}
for (int i = 0; i < N; i++) {
int tmp = 0;
// i보다 앞쪽에 있으면서
for (int j = 0; j < i; j++) {
// i번째 값보다 작은 원소들 중에
if (arr[j] < arr[i]) {
// dp 테이블의 최댓값 구하기
tmp = max(tmp, dp[j]);
}
}
dp[i] = tmp + 1; // 거기에 1을 더해서 dp 테이블 갱신
ans = max(dp[i], ans); // dp 테이블의 최댓값 갱신
}
cout << ans;
return 0;
}1) 배열 전체를 순회하면서 - O(N)
2) 자신보다 앞에 있는 원소 중에서, 자신보다 크기는 작은데 dp 값은 최대인 원소를 찾는다. - O(N)
따라서 시간복잡도가 O(N^2) 이므로, N의 크기가 10^4보다 작을 때만 사용하는 게 좋다.
2번 과정에서 최적해의 위치를 찾는 데 걸리는 시간을 O(logN)으로 줄일 수 있는 방법에 대해 알아보자!
O(NlogN) 풀이
https://www.acmicpc.net/problem/12015
이번 문제는 입력 크기의 최댓값이 10^6이다.
이번에는 LIS 길이 정보를 저장하기 위한 배열이 하나 더 필요하며, 이를 vector L이라고 해보자. 그러면 다음과 같은 알고리즘을 생각해볼 수 있다.
- arr 배열을 순회하면서
- L이 비어있다면 arr[i]를 push한다.
3-1. L의 마지막 원소보다 arr[i]가 더 크면 L에 push한다.
3-2. 그렇지 않으면, lower_bound(L.begin(), L.end(), arr[i]) 위치의 값을 arr[i]로 바꾼다.
💡 lower_bound(first, last, value) 함수란?
오름차순으로 정렬된 배열의 [first, last) 범위에서 value 이상의 값이 처음 등장하는 위치를 반환한다. 만약 배열의 모든 원소가 value보다 작다면, 마지막 원소 바로 다음 위치를 반환한다.
이번에도 예시를 통해 이해해보자!
{9, 8, 8, 9, 11, 10, 14} 라는 배열이 주어졌다고 가정한다.
i = 0
벡터 L이 비어있으므로 arr[0]을 push한다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 9 |
i = 1
L의 마지막 원소보다 arr[1]이 작기 때문에, lower_bound(L.begin(), L.end(), arr[1])가 반환하는 위치의 값을 arr[1]로 바꾼다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 |
i = 2
L의 마지막 원소와 arr[2]가 같기 때문에, lower_bound(L.begin(), L.end(), arr[2])가 반환하는 위치의 값을 arr[2]로 바꾼다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 |
i = 3
L의 마지막 원소보다 arr[3]이 크기 때문에 L에 push한다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 | 9 |
i = 4
L의 마지막 원소보다 arr[4]가 크기 때문에 L에 push한다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 | 9 | 11 |
i = 5
L의 마지막 원소보다 arr[5]가 작기 때문에, lower_bound(L.begin(), L.end(), arr[5])가 반환하는 위치의 값을 arr[5]로 바꾼다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 | 9 | 10 |
i = 6
L의 마지막 원소보다 arr[6]이 크기 때문에 L에 push한다.
| arr | 9 | 8 | 8 | 9 | 11 | 10 | 14 |
|---|---|---|---|---|---|---|---|
| L | 8 | 9 | 10 | 14 |
따라서, LIS의 길이는 벡터 L의 길이인 4가 된다!
lower_bound는 이진탐색 기반의 함수이므로 시간복잡도가 O(logN)이다. 따라서, 위 풀이 과정의 전체 시간복잡도는 O(NlogN)이 된다.
한 가지 주의할 점은 벡터 L은 LIS의 '길이'에 관한 정보만 나타내는 배열이지, 절대 LIS의 요소를 직접적으로 포함하는 배열이 아니라는 것이다!
예를 들어, {9, 10, 8}이라는 배열에서 LIS의 길이는 2, 그 수열은 {9, 10}이지만, 벡터 L에는 {8, 10}이 저장된다.
LIS 길이와 수열 구하기
O(N^2)
https://www.acmicpc.net/problem/14002
O(NlogN)
