개요
수열 arr의 모든 부분수열중 원소가 모두 증가하는 부분수열의 최대길이를 구하려는 문제가 있을때,
단순히 전부 그리디방법으로 탐색시, N N회의 연산이 필요하나,
DP를 이용하여 N N (1/2)로 절반으로 줄이거나
BS(Binary Search)를 이용하여 N log N 의 연산만에 해결 가능하다.
그외에 세그먼트트리를 이용한 방법도 있으나 여기선 DP, BS 두가지경우만 소개하려고한다.
DP를 이용한 LIS 알고리즘
DP[i] = "0~i원소로 이루어진 부분수열내의 LIS의 길이" 로 정의하면,
Bototm-up으로 DP[i]를 구해두면, i보다큰 모든인덱스k에서 DP[i+k]이 arr[i] < arr[i+k]관계를 만족하면
DP[i+k] = DP[i] + 1이라는 간단한 수식을 생각해볼 수 있다.
따라서 알고리즘으로 구현하면 아래와 같다.
int LISwithDP(vector<int>& arr) {
if (arr.empty()) return 0;
vector<int> dp(arr.size());
for (int i = 0; i < arr.size(); i++) {
//i보다 작은 j에대해 모두 감소하는관계라면
//최소한 자기자신으로만 이루어진 LIS가 존재가능
dp[i] = 1;
for (int j = 0; j < i; j++)
if (arr[j] < arr[i])
dp[i] = max(dp[i], dp[j] + 1);
}
return dp[arr.size() - 1];
}이때 arr의 모든 부분수열에서 LIS는 최소한 자기자신만으로 이루어질 수 있으므로 초깃값으로 1을 지정해주어야한다.
이분탐색을 이용한 LIS 알고리즘
먼저 수열arr을 전부 순회하기에 O(N)이 소요되는데,
이때 각 원소마다
list배열에서 lower_bound로 적절한 위치를 찾아서 (lower_bound알고리즘 >> https://velog.io/@cldhfleks2/Binary-Search)
arr의 원소를 기록하기에lower_bound를 사용해서 O(log N)
총 O(N log N)의 시간복잡도 안에 해결 가능해진다.
자세히 살펴보자.
arr과 같은 크기의 lis 배열을 준비한다.
이제 두가지 동작을 수행할것이다.
- lis의 끝원소보다 arr[i]가 크면 lis끝원소 뒤에 추가한다.
- lis의 끝원소보다 작거나 같으면 lower_bound를 찾아 그 위치에 arr[i]를 덮어씌운다.
arr[0]~arr[2] 은모두 증가하므로 lis에 차례대로 넣었다.
이제 arr[3]을 보는데, 이것은 lis의 끝원소 50보다 작으니 lower_bound위치에 arr[3]을 덮어씌운다.
그리고 arr[4]를 보면 이 또한 작거나 같으므로 lower_bound인 lis[1]에 덮어씌운다.
arr[5]는 크므로 lis맨뒤에 추가한다.
arr[6]은 60보다 작으니 lower_bound인 lis[3] 에 덮어씌웁니다.
이로써 알 수 있는것이 lis에 lower_bound를 찾아 원소를 덮어씌웠기때문에,
arr[2] = 50이 lis의 맨뒤에 존재했다면 arr[6]을 추가하지 못했으니 LIS가 아니게 됩니다.
따라서 매번 lis 배열이 증가하는 수열이 될수있도록 최적의 위치를 찾도록, 큰값은뒤, 작거나같은값은 적절한위치를 찾아 덮어씌우기에 LIS를 유지 할 수 있습니다.
이제 코드를 보자.
//아래의 LIS에 사용될 LowerBound함수
int LowerBound(vector<int>& lis, int k) {
int L = 0, R = lis.size() - 1;
while (L < R) {
int M = (L + R) / 2;
if (k <= lis[M])
R = M;
else
L = M + 1;
}
return R;
}
//2. LowerBound를 이용하여 LIS를 구하는 함수
//만들어진 LIS배열은 순서가 뒤섞인,
//그저 arr의 어떤 요소가 LIS를 이루는지만 확인 가능
int LISwithBinarySearch(vector<int>& arr) {
if (arr.empty()) return 0;
vector<int> lis(arr.size());
lis.push_back(arr[0]);
for (int i = 1; i < arr.size(); i++) {
if (lis.back() < arr[i])
lis.push_back(arr[i]);
else //lis에 arr[i]가 들어갈 적절한위치를 LowerBound로 찾아서
//해당위치에 arr[i]를 저장
lis[LowerBound(lis, arr[i])] = arr[i];
}
return lis.size(); //만들어진 lis 배열을 리턴합니다.
}이방법은 DP를 활용한 LIS와 달리, 그 길이와 LIS를 이루는 원소가 무엇인지 확인 가능합니다.
다만 만들어진 LIS배열의 원소는 원래 arr에서 옮겨진 순서가 섞여있다.
관련문제
https://www.acmicpc.net/problem/11053 >> https://velog.io/@cldhfleks2/11053
