8-D 북서풍

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 강사님 , 3시간 가량 이 문제를 붙잡아도 도저히 이해가 되지 않네요.. ㅜ - ㅜ 아래 코드에서 find_index 함수의 역할이 너무 어려워요. 왜 update(find~+1) 을 하는건지, find_index 함수는 뭘 출력하는건지 모르겠어요. v[i].second의 인덱스 출력은 아닌 것 같고, v[i].second의 개수도 아닌 것 같고... 강의를 3번 듣고, 구글링도 많이 해봤는데.. 혼자 계속 고민해봤자 답이 안나올 것 같아요. <아래 코드 출력값> -10 -10 10 10 -10 => 1 10 => 2 -10 => 1 10 => 2 ll ret = 0; cout << " " << v[0].second << " => " << find_index(v[0].second) << " "; update(find_index(v[0].second) + 1, 1); for (int i = 1; i < n; i++) { int idx = find_index(v[i].second) + 1; cout << " " << v[i].second << " => " << find_index(v[i].second) << " "; ret += 1LL * sum(idx); update(idx, 1); }

큰돌 · Answer

안녕하세요 구재연님 ㅎㅎ 먼저 여기까지 오시느라 수고 많으셨습니다. 아래 코드에서 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 & _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라는 인덱스를 반환합니다. 자 좀 더 쉬운 예제로 들어볼게요. 1 3 5 1 4 2 3 3 이거를 기반으로. #include #define max_n 75004 typedef long long ll; using namespace std; int n, x, y, t; vector tree, _y; vector> 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 & _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 "; cout << a[i].second << " : " << find_index(_y, a[i].second) << " "; int idx = find_index(_y, a[i].second) + 1; ret += 1LL * sum(idx);update(idx, 1); } cout << ret << " "; } 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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.