내가 사용하는 STL (6) - lower_bound & upper_bound & 좌표압축

이번에는 자료구조의 성격을 띄고 있는 STL이 아닌 함수의 성질(?)을 띄고 있는 STL에 대해서 말하려고 한다. 바로 lower_bound와 upper_bound이다. lower_bound를 확실히 정리하려는 이유는 이상, 이하, 초과, 다음이 맨날 햇갈려서 항상 한번 긴가민가 하면서 코딩해보고 수정을 하기 때문이다. 엄청나게 시간소모를 하는것은 아니지만, 답이 틀릴때 마다 lower_bound에 확신이 없어 한 번 검토해야하는 것은 확실히 스트레스이다. 

※ 배열은 1-base 기준입니다.

lower_bound

lower_bound는 범위내의 정렬된 자료들 내에서 원하는 원소보다 같거나 큰 첫 번째 위치를 찾아준다. 예를 들어서 벡터에 2 2 4 5 7 9가 있고, 이 벡터 전체에 대해서 7을 기준으로 lower_bound를 하면 백터 속의 7의 위치를 반환해준다. 이렇게 작동하는 함수이다. 

시간복잡도는 이분탐색의 형식으로 log에 작동하며 당연히 정렬이 되어 있는 상태여야 작동이 가능하다. 다시말해서 lower_bound가 제대로 작동하는 조건은 찾는 범위가 기준에 따른 정렬이 되어있어야 한다는 것이다. 

upper_bound는 원소보다 큰 첫 번째 위치를 찾아준다. 즉, upper bound에서는 벡터 2 2 4 5 7 9 에 대해서 7을 기준으로 탐색하면 9의 위치를 반환해 준다는 것이다.

문법

lower_bound(starting point,ending point,value)
lower_bound(v.begin(),v.end(),k)

가장 기본적인 형태이다. lower_bound에 3개의 인자가 들어가며, 3개의 인자는 각각 범위의 시작지점, 끝지점, 값을 나타낸다. 이때 구간은 정렬되어있는 상태이며, 그 구간을 구성하고 있는 원소에 대한 정렬기준은 정의가 되어있어야 한다. 즉 vector<poi> v 와 같이 정렬기준이 정의되어있지 않은 경우에 대해서는 실행을 할 수가 없게 된다.

lower_bound(arr+1,arr1+1+n,k)

이는 n개짜리 배열에 대해서 lower_bound를 실행하는 코드다. 

sort(arr+1,arr+1+n)
sort(v.begin(),v.end())

3개의 인자로 lower_bound를 한다면 이미 정렬기준이 완벽하게 정의되어 있다는 것이기 때문에 2개의 인자로 정렬이 가능하다. lower_bound를 실행하기 전에는 항상 위와 같은 코드가 있어서 정렬을 시켜주어야 한다.

---

lower_bound(starting point,ending point,value,sort function)

4개짜리 인자에 대해서는 마지막 인자에 정렬함수가 들어가게 된다. 이때는 구간의 정렬기준을 잡아주는 것이다. 

한가지 예시를 들어보자. 간선을 가중치에 대해서 정렬한다고 하자. 그러면 아래의 코드와 같은 일련의 과정으로 진행된다. 

strcut poi{
    ll u,v,c; 
};
poi arr[1010101];

bool sf(poi a,poi b){
    return a.c<b.c;
}

int main(){
    //배열에 간선 집어 넣음
    ll n;
    poi x;
    sort(arr+1,arr+1+n,sf);
    lower_bound(arr+1,arr+1+n,x,sf);
}

같은 함수의 비교 기준을 사용하여 정렬과 lower_bound를 둘 다 진행한 모습이다. 이렇게 일관된 기준을 가지고 실행을 해야 찾을 수 있다.

---

ll idx=lower_bound(v.begin(),v.end(),k)-v.begin();

보통 이런식으로 위치를 인덱스로써 값을 가져오게 된다. 이러면 k이상의 값이 등장하는 최초의 위치가 v[idx]가 된다. 번째로는 idx+1번째 원소이다. 이 부분이 헷갈린다면 v에 -inf를 넣어서 

ll idx2=lower_bound(arr+1,arr+1+n,k)-arr;

배열에서 인덱스를 가져오면 벡터에서의 값보다 1이 큰 값이 나오게 된다. 물론 1-base의 형태이기 때문에 idx2=idx+1 이지만 v[idx]=arr[idx2]이다.

---

좌표 압축

숫의 개수는 100000개인데, 수의 범위는 10^18이나 10^9인 경우가 있다. 이때 segment tree 등을 사용해야 한다던지 등의 이유로 수들의 순서관계만이 필요할 때가 있다. 이럴 때 좌표를 압축해서 인덱싱하는 것을 좌표압축기법이라고 한다.

위에서 제대로 설명을 못한 것 같아서 예시를 들려고 한다. 1 3 9 7 15 의 수 리스트가 있으면, 이 리스트의 수들을 
1 2 4 3 5로 바꿔서 저장하는 것이다. 공간 복잡도 제한의 이유로 이렇게 줄여놓고 계산한 후에 나중에 다시 복원하면 된다.

좌표 압축 하는 법

vector에서는 인덱스를 1부터로 만들기 위해서 보통 -inf를 집어넣고 좌표압축을 하는 편이다. 

vector<ll> v;
ll arr[1010101];

int main(){
   for(i=1;i<=n;i++){
   	scanf("%lld",&arr[i]);
    v.push_back(arr[i]);
   }
   v.push_back(-inf);
   sort(v.begin(),v.end());
   v.erase(unique(v.begin(),v.end()),v.end());
   for(i=1;i<=n;i++){
   	arr[i]=lower_bound(v.begin(),v.end(),arr[i])-v.begin();
   }
    
}