8-D 펜윅트리 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

8-D

작성

379

안녕하세요 강사님

문제의 풀이 아이디어는 이해가 되는데요.

펜윅트리를 사용한 부분에서 궁금한 부분이 y좌표가 같은 경우를 해결하는 부분이 잘 이해가 되지 않습니다.

_y를 이분탐색해서 인덱스를 찾는 과정 쪽이 명쾌하게 이해가 되지 않아서요 ㅜㅜ

c++코딩-테스트

답변 2

이희수

같은 의문점이 생겨 질문드립니다!

y좌표가 같은 두 점이 존재할 경우, find_inedx() 함수를 사용하여 반환되는 인덱스가 동일한데, 로직에 지장이 없는걸까요?

큰돌

지식공유자

안녕하세요 희수님 ㅎㅎ

먼저 문제 지문을 보시면 다음과 같이 되어있습니다.

두 섬의 좌표가 같은 경우는 없다. (-109 ≤ xi, yi ≤ 109)

하지만 y좌표가 같은 경우는 존재하죠.

find_index부분을 볼까요?

        update(find_index(_y, a[0].second) + 1, 1);
        for(int i = 1; i < n; i++){
            int idx = find_index(_y, a[i].second) + 1;
            ret += 1LL * sum(idx);update(idx, 1);

이 find_index가 담당하는 것은 해당 idx로 부터 얼만큼의 섬이 있냐를 체킹하는 기준을 찾는 것 입니다.

예를 들어

9, 9, 9 이 3개의 같은 지점이 있다면 -> 해당 9이상의 좌표는 총 3개가 되는 것이고 -> ret에 더해지는 것은 3개가 되는 것이기 때문에 로직상 지장이 없습니다.

감사합니다.

큰돌

지식공유자

안녕하세요 재윤님 ㅎㅎ

int find_index(const vector<int> & _y, int value){
    int lo = 0, hi = _y.size() - 1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(_y[mid] == value) return mid;
        if(_y[mid] < value) lo = mid + 1;
        else hi = mid - 1;
    }
}

이부분 말씀하시는거죠?

이 문제는 y의 좌표를 카운팅해야 하는 것입니다. a라는 값 위에 y가 "몇개" 있냐라는 카운팅을 해야하는 것이죠.

자 일단은 y는 하나하나 -10^9 ~ 10^9까지의 범위를 가집니다. 따라서 이걸 카운팅배열로 저장할수도 없는 것이죠.

예를 들어 a[1000000000] = 1 이런식으로 말이죠.

그렇기 때문에 그저 vector v에다가 집어넣고 여기에서 해당 y에 관한 지점을 이분탐색으로 고릅니다. 물론 그냥 선형적으로 탐색할 수도 있지만 이미 정렬이 되어있기 때문에 이분탐색으로 해야 더 빠르기 때문에 이분탐색으로 해당 좌표를 찾는 것입니다.

        for(int i = 1; i < n; i++){
            int idx = find_index(_y, a[i].second) + 1;
            ret += 1LL * sum(idx);update(idx, 1);
        }

또한 좌표압축을 하는건데 -10^9 ~ 10^9 을 1 ≤ n ≤ 75000 이러한 범위를 가지는 idx로 변환을 시켜서 넣는 것입니다.

그림을 그려보면 다음과 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변

8-D 펜윅트리 질문