8-D 북서풍

안녕하세요 구재연님 ㅎㅎ

먼저 여기까지 오시느라 수고 많으셨습니다.

아래 코드에서 find_index 함수의 역할이 너무 어려워요.

왜 update(find~+1) 을 하는건지,

find_index 함수는 뭘 출력하는건지 모르겠어요.

이코드 말씀이시죠?

        for(int i = 0; i < n; i++){
            cin >> x >> y;
            a.push_back({x, y * -1});
            _y.push_back(y * -1);
        }
        sort(a.begin(), a.end());
        sort(_y.begin(), _y.end());
        ll ret = 0;
        update(find_index(_y, a[0].second) + 1, 1);

_y는 y좌표들이 반대로 담깁니다.

_y = -1 * y좌표리스트

a[0].second가 의미하는 것은 y * -1가 들어간 값입니다.

해당 값을 찾아서 인덱스를 반환합니다.

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;
    }
}

이미 sort가 되어있기 때문에 이분탐색을 쓸 수가 있습니다.

예를 들어

-1, -2, -3, -4가 들어가있고 -3을 찾는다면 2라는 인덱스를 반환합니다.

자 좀 더 쉬운 예제로 들어볼게요.

이거를 기반으로.

#include <bits/stdc++.h>
#define max_n 75004
typedef long long ll;
using namespace std;
int n, x, y, t;
vector<int> tree, _y;
vector<pair<int, int>> a;

int sum (int idx){
    int ret = 0;
    while(idx > 0){
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
void update(int pos, int value){
    int idx = pos;
    while(idx <= n){
        tree[idx] += value;
        idx += (idx & -idx);
    }
    return;
}
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;
    }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    cin >>t;
    while(t--){
        cin >> n;
        a.clear(); _y.clear();
        tree.clear();
        tree.resize(n + 1);
        for(int i = 0; i < n; i++){
            cin >> x >> y;
            a.push_back({x, y * -1});
            _y.push_back(y * -1);
        }
        sort(a.begin(), a.end());
        sort(_y.begin(), _y.end());
        ll ret = 0; 
        update(find_index(_y, a[0].second) + 1, 1);
        for(int i = 1; i < n; i++){
            cout << "index\n";
            cout << a[i].second << " : " << find_index(_y, a[i].second) << "\n";
            int idx = find_index(_y, a[i].second) + 1;
            ret += 1LL * sum(idx);update(idx, 1);
        }
        cout << ret << "\n";
    }
	return 0;
}

디버깅 코드는 앞의 코드와 같습니다.

첫번째 인덱스를 제외하고 출력하는거라 이렇게 출력이 될 겁니다.

index

-2 : 1

index

-1 : 2

이 의미는.

-2를 _y 안에서 찾아줘.

가 되죠.

_y는 -3, -2, -1이 들어가있겠죠?

이 안에서 -2는 1을. -1는 2를 반환하게 됩니다.

그 이후 해당 인덱스 + 1에 해당 하는 펜윅트리를 업데이트합니다.

이 때 + 1을 하는 이유는 인덱스는 0 ~ n - 1이렇게 반환될텐데

펜윅트리는 1부터 시작하므로 + 1을 해줍니다.

업데이트를 왜하냐?

펜윅트리를 통해 우리는 어떤 정점에서 그 이전에 몇개의 정점이 얼마나 있는지를 쉽게 파악할 수 있습니다.

예를 들어

1 1 1 1 3이라고 했을 때 3 뒤에는 1이 4개가 있죠?

이를 빨리 파악할 수 있게 하는 자료구조가 펜윅트리입니다.

1이라는 값에 +1을 함으로써 결국 1이라는 값은 4만큼의 크기를 가지고 3에서 그 밑에 있는 수를 끄집어낸다 했을 때

sum이라는 함수로 4개를 끄집어낼 수 있는 것이죠.

다시 예를 들면

1 1 1 1 2 2 3 이렇게 되어있을 떄

1 : 4, 2 : 2 이런식으로 되어서

sum()을 기반으로

3밑에 6개가 있네 를 쉽게 뽑아낼 수 있게 되는 것입니다.

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

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

감사합니다.

강사 큰돌 올림.

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