개요
-
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
-
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
접근 방식
세그먼트 트리 사용하는 방식
-
백준 11055번: 가장 큰 증가하는 부분 수열 문제 처럼
Dp로 풀어보려했으나 범위가 너무커서 시간초과가 났다.
그 후 세그먼트로 접근해보려 했으나
어떤식으로 접근해야 하는지 감이 안 잡혔다. -
찾아본 방법으로는 일단 값을 받은 다음,
<값, 값의 index>의 pair 형태로 저장을 한다. -
이 pair의 값을 기준으로 오름차순으로 정렬을 한다.
정렬된 pair를 작은 값부터 순회하며 해당 값의 index를 방문한다. -
구간 [0,index]의 최대값을 세그먼트트리를 탐색해 찾는다.
세그먼트트리는 0으로 초기화 되어있으므로 해당 값에 +1을 한 후, 세그먼트 트리의 리프노드에 저장 후 조상노드들을 갱신한다. -
세그먼트트리의 조상 노드들을 갱신할때는 자식노드들의 최대값으로 갱신한다.
-
예제 문제로 봐보자.
예제값으로 제공된 10 20 10 30 20 50 수열이 있다.정렬해보면
정렬시-> 10 10 20 20 30 50
인덱스 2 0 4 1 3 5
이분탐색 사용하는 방식
-
간단하다. 첫번째 값을 벡터에 넣는다.
-
그 다음 값이 벡터의 끝값과 같은지 비교하여 벡터의 끝값보다 크다면 push_back연산을 한다.
-
작다면 현재값보다 큰 값 중 인덱스 제일 작은 값을 이분탐색을 이용해 찾는다.
int binarySearch(int elem) { int low = 0, high = v.size()-1,mid=0; while (low+1 < high) { mid = (low + high) / 2; if (v[mid] < elem) low = mid; else high = mid; } //v.size()가 2일경우 index 1의 원소를 바로 반환하는걸 방지하기 위함 if (v[low] >= elem) { return low; } return high; } -
넣고 판단하는 과정을 반복하다가 결국 벡터내부에 있는 값들이 제일 긴 증가하는 부분 수열이다.
-
벡터 길이 출력하면 완료.
세그먼트 트리 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//2^21
int segTree[2097152];
int N,firstLeafNodeIdx=1,largestIdx=0,lis=0;
//값, 인덱스
vector<pair<int,int>> v;
//벡터 v 정렬시 비교용 함수.
bool cmp(pair<int,int> a, pair<int,int> b) {
if (a.first != b.first) return a.first < b.first;
//만약 중복값이면 인덱스 큰값을 앞으로 보내서 중복값일때 길이 증가하지 않도록 처리
else return a.second > b.second;
}
//n번째 리프노드 값 k로 설정 후 , 조상 노드로 거슬러 올라가며 더큰값으로 갱신해주는 함수
void SetAncestorNode(int n,int k) {
n += firstLeafNodeIdx;
segTree[n] = k;
while (n > 1) {
n /= 2;
segTree[n] = max(segTree[2 * n], segTree[2 * n + 1]);
}
}
//[targetL,targetR]의 최대값을 구하는 함수
long long Largest(int targetL, int targetR, int nodeNum, int curL, int curR) {
if (curR < targetL || targetR < curL) return 0;
if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
long long mid = (curL + curR) / 2;
return max(Largest(targetL, targetR, nodeNum*2, curL, mid) , Largest(targetL, targetR, nodeNum*2+1, mid + 1, curR));
}
void ReadjustTree() {
int tmp = 0,result=0;
//정렬된 벡터에서 순회하며
for (auto iter : v) {
//tmp= 정렬된 벡터에서 순회하는 값의 현재 인덱스
tmp = Largest(0, iter.second, 1, 0, firstLeafNodeIdx - 1) + 1;
result = max(result, tmp);
//작은값부터 해당 인덱스 값에서 조상노드로 올라가며 갱신
SetAncestorNode(iter.second, tmp);
}
cout << result;
}
void Input() {
int tmp;
cin >> N;
//firstLeafNodeIdx 구하기
while (firstLeafNodeIdx < N) {
firstLeafNodeIdx *= 2;
}
for (int i = 0; i < N; i++) {
cin >> tmp;
v.push_back({ tmp,i });
}
sort(v.begin(), v.end(), cmp);
ReadjustTree();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}이분탐색 코드
//////////////////////////////////////////////// using Binary Search
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
int binarySearch(int elem) {
int low = 0, high = v.size()-1,mid=0;
while (low+1 < high) {
mid = (low + high) / 2;
if (v[mid] < elem) low = mid;
else high = mid;
}
//v.size()가 2일경우 index 1의 원소를 바로 반환하는걸 방지하기 위함
if (v[low] >= elem) {
return low;
}
return high;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N=0,tmp=0,idxToChange;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tmp;
//비어있거나 벡터의 끝값보다 이번 tmp값이 더 크다면 push_back
if (i == 0 || v.back()<tmp)
v.push_back(tmp);
//아니라면 tmp값보다 크거나 같은 원소중 제일 인덱스 큰 원소를 tmp로 교체한다.
else {
idxToChange = binarySearch(tmp);
v[idxToChange] = tmp;
}
}
cout << v.size();
}문풀후생
이분탐색은 몇가지 예를 들어 시도해보니 직관적으로 좀 이해가 가능했다.
만약 1 6 2 3 4 이런식이라고 하자.
벡터에 1 6 들어간 후, 어차피 1 6이나 1 2나 수열의 길이는 같으면서
2가 더 긴 부분수열의 가능성이 있으므로 2로 교체한다.
따라서 6을 2로 교체후 3 4 푸시해서 1 2 3 4 이런식으로 제일 긴 수열을 얻기가 가능하다.
하지만 세그먼트 트리 풀이는 처음봤을 땐 잘 이해가 안 갔다.
여러번 생각해보니 이해가 갔는 데 쉽지 않았다..
값 x와 인덱스 i를 pair로 묶고 값을 정렬 후, 값의 순서대로
해당 값의 인덱스 i를 방문하여 [0,i]구간의 최대값에 +1을 해줘서
트리를 갱신한다.
잘 생각해보니 값은 이미 정렬된 상태이다.
정렬된 값을 차례대로 순회하며
세그먼트 트리의 리프노드에서 해당 값들의 인덱스를 찾아가면
아직 갱신이 안되어 초기값인 0이 들어가 있다.
따라서 [0,i]의 최대값은 결국 자기 값보다 작은 값의 최대값을 구하는 것이고, 해당 값은 결국 인덱스 0부터 i-1까지의 구간 길이 중 최대값이므로 +1을 해서 저장하는 방식인 것이다.
