LIS는 이분탐색을 사용하는 기법이다.
Longest Increasing Subsequence의 약자로써, 가장 긴 증가하는 부분 수열을 의미한다.
이에 대해 이해하면, 사실 가장 긴 감소하는 부분 수열에도 똑같이 응용 가능하다.
[어떤 수를 어디에 놓을지]를 이분탐색으로 해결하는 것이 핵심이다.
위의 그림과 같이, [4, 2, 1, 5, 6, 3] 이라는 수열이 있다고 예를 들자. 이때 가장 긴 증가하는 부분 수열을 찾고자 할 때, 위에 일일이 적은 대로 앞에서부터 하나씩 골라서 확인해볼 수 있을 것이다. 그럼 방식은 2중 for-loop구조를 갖게 되므로, O(n^2)의 시간복잡도를 갖게 된다.
당연히 좋은 방법이 아니다.
위의 그림을 보자. 가장 긴 증가하는 부분 수열을 담을 LIS벡터 또는 배열을 선언한다. 먼저 이 공간이 비어있으면 첫번째 원소는 프리패스로 그냥 넣는다. 그리고 다음에 오는 2를 4와 비교해서 처리한다. 4보다 2가 작으니 2로 교체해준다. 당연히 처음 시작하는 수가 작아야 다음에 큰 수들을 많이 받을 수 있기 때문이다. 여기서 이 2를 넣어줄 위치를 찾는 과정에서 이분 탐색을 사용한다.
본 내용은 이전 이분탐색 관련 포스팅에서 한번 간략하게 소개를 해두었다.
1이 2보다 작으니 1로 교체되고, 이후의 5, 6은 그대로 삽입된다. 마지막 3은 5를 교체하여 최종적으로는 [1, 3, 6]이 된다.
어떤 수가 LIS내에서 어디에 놓일지, 어떤 수를 대체해줄 지를 찾는 과정에서 위와 같은 이분탐색이 사용된다. 현재까지 완성된 LIS배열의 양 끝 위치의 인덱스를 s, e에 저장하고 주어진 값이 놓일 곳을 찾는 것이다. 현재까지 완성된 LIS배열은 정렬된 형태이기에 이 방법이 가능하다! 아래는 위와 똑같은 내용을 코드로 구현한 것이다.
while(s<e){
mid=(s+e)/2;
if(arr[mid]>=given)e=mid;
else s=mid+1;
}LIS가 정렬된 형태이기에 중간값을 보고 판단하여 절반의 범위로 줄여나갈 수 있게된다.
그래서 매 숫자에 대해서 log n(이분탐색)의 연산을 하게 되고, 모든 원소(n)에 대해 이 과정을 수행하면
총 O(n log n)의 시간복잡도를 갖게 된다.
위처럼, 직접 이분탐색을 구현해도 되고,
C++의 lower_bound, upper_bound나 Python의 bisect_left, bisect_right를 사용해도 좋다.
그리고 LIS를 공부하면, LIS를 구성하는 실제 원소들까지도 구해야 어느 정도의 깊이를 갖추었다고 말할 수 있다.
백준 2352번 문제를 예시로 들어보겠다.
아래의 코드를 보면
varr는 문제의 입력값이 담기는 벡터이고, nv는 LIS벡터이다.
lower_bound를 통해 nv에 LIS를 구성한다.
그리고 backtrack이는 스택을 두었는데, 여기에 각 값들의 nv내에서의 인덱스와 함께 pair로 묶어서 저장해둔다.
vector<int>nv,varr;
stack<pair<int,int>>backtrack;
for(int i=1;i<(int)varr.size();++i){
idx=lower_bound(nv.begin(),nv.end(),varr[i])-nv.begin();
if(idx==(int)nv.size())nv.push_back(varr[i]);
else nv[idx]=varr[i];
// LIS backtrack
backtrack.emplace(idx,varr[i]);
}
idx=(int)nv.size()-1;
while(!backtrack.empty()){
if(backtrack.top().first==idx){
nv[idx]=backtrack.top().second;
idx--;
}
backtrack.pop();
}(줄맞춤이 왜 안되는지 모르겠다 ㅡㅡ;)
그리고 스택을 비워나가면서 LIS벡터의 가장 뒤에서부터 값을 갱신해나간다.
1, 2, 3, 4 ,5 라는 수열이 있다면,
LIS벡터에 [1, 2, 3, 4, 5]라고 저장되었을 것이고,
backtrack안에는 [(0,1), (1,2), (2,3), (3,4), (4,5)]로 저장될 것이다. (필자의 코드는 LIS벡터가 비어있을 때, 첫 값을 그냥 넣었는데, 원래는 처음부터 인덱스를 받아서 backtrack에 저장해야 한다.)
그리고 스택구조로 되어있으므로 (4,5)부터 빠져나올 것이고, idx=4부터 시작하고, 하나씩 매칭 되면서 그대로 [1,2,3,4,5]로 유지된다.
하지만 [4, 2, 1, 5, 3]은 어떨까?
위와 같이, LIS배열을 찾는 과정과 backtrack스택에 담기는 값들을 정리하였다. LIS배열의 길이는 2가 되고, backtrack스택을 비워가면서 실제 배열을 찾는 과정에서 시작할 인덱스는 1 (LIS배열의 길이 - 1)이 된다.
이제 idx=1부터 시작해서 backtrack스택에서 하나씩 빼면서 idx와 stack.top().first가 같은지 비교한다. 같다면, LIS배열에 stack.top().second를 기록함으로써 값을 갱신한다. 그리고 반드시 idx--를 해서 같은 위치의 값을 다시는 찾지 않는다!
이제 idx=0이므로 (1, 5)는 일치하지 않아서 그대로 버린다. 그 다음 (0, 1)은 idx=0과 일치하므로 LIS배열 안에 값을 갱신해준다. 그리고 idx가 -1이 되므로, 스택에 있는 나머지 모든 값들은 전부 매칭이 안돼서 버려진다.
이번 예시에서는 처음에 찾은 LIS배열이 실제 원소를 찾아본 후에도 그대로 유지되어 달라진 게 없었는데, 다른 예시를 몇가지 더 만들어서 확인해보기 바란다. 결국 이 방법의 핵심은 LIS내에 가장 마지막으로 갱신된 값이 가장 확실한 답이라는 점이다. 그래서 가장 마지막에 들어온 값이 가장 먼저 나오는 스택 구조를 통해, 가장 뒤의 인덱스부터 값을 확정해나가는 것이다.
2, 7, 1이라는 수열을 생각해보자.
LIS배열은 [1, 7]이 될것이고,
스택을 비워나가면 [2, 7]이 될 것이다.
즉, 7이 나올 때까지는 (7은 인덱스 1) 스택에 있는 모든 앞선 인덱스 (1은 인덱스가 0)를 가진 값들이 전부 버려진다. 만약에 2, 7, 1, 5였다면 [1, 5]가 되었을 텐데, 7이 갱신되지 않았기에 1이 LIS배열에서 2를 덮어썼어도 의미가 없었던 것으로 볼 수도 있는 것이다.
그리고 2번자리 값이 그 자리에 올 수 있었던 것은 바로 이전의 1번자리 값 덕분이다. 즉 LIS도 값이 작은 것부터 쌓여간 것이므로, LIS의 길이를 늘려주지 않는 (그저 앞자리의 숫자만 바꿔주는) 값은 스택에서 뽑을 때 버릴 수 있는 것이다.
여기서 보다시피 실제 LIS를 구성하는 원소를 구할 때는 답이 여러 개 있을 수 있다.
<연습 문제>
