CP Algorithm & Knowledge (30) 썸네일형 리스트형 LIS와 multiset 사실 이게 뭔진 모르겠지만 나 스스로 뭔가 흥미로운 방법으로 문제를 풀고 있는 것 같아 기록해둔다. 일단 이 문제를 보자. https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의를 모두 진행할 수 있는 회의실의 최소를 구하는 것이다. 나는 이렇게 풀었다. 1. 빨리 끝나는 순서로 정렬한다. 끝나는 순서가 같으면 시작하는 시간이 빠른 순서로 정렬한다. 2. multiset을 준비한다. 첫 번째 회의는 trivial case로 두어 첫 번째 회의.. pb_ds의 간단한 고찰 - 트리 구현체 PS를 좀 오래 한 사람이라면 pb_ds의 존재를 알고 있을 것이다. 그리고 보통 트리의 구현체로 r-b 트리인 rb_tree_tag를 쓸 것이다. 하지만 r-b 트리 외에도 스플레이 트리 구현체인 splay_tree_tag가 존재한다. C++ 상에서 구현된 r-b 트리는 상수가 크다고 알려져 있는데 그럼 스플레이 트리를 대신 쓰면 성능이 좀 좋아질까? 그래서 해보았다. 백준 2104 - 스플레이 트리 http://boj.kr/1404da72672b4c429dfc8f2504ff4558 백준 2104 - r-b 트리 http://boj.kr/b9c4a1b73379447192b2c6153f223525 무려 스플레이 트리가 2배 더 빠르다! 그러면 다른 문제로 확인해보자. 백준 1572 - 스플레이 트리 ht.. 2차원 평면에서 모든 점 쌍의 유클리드 거리 합 구하기 오늘은 이런 문제를 풀어보자. 2차원 직교 좌표계에서 N개의 점이 있다. ($N \leq 10^{6}$) 좌표가 동일한 두 점이 존재할 수 있다. i번째 점을 $p_{i}$라 하고 i번째 점과 j번째 점의 유클리드 거리 제곱을 $dist(p_{i}, p_{j})$라고 했을 때 다음을 구하시오. $\sum\limits^{N - 1}_{i = 1}\sum\limits^{N}_{j = i + 1} dist(p_{i}, p_{j})$ 지금 생각할 수 있는 간단한 방법은 $\binom{N}{2}$의 쌍의 거리를 일일이 계산하는 것이다. 하지만 그런 걸로 되면 이 글을 쓸 필요도 없다. N이 100만까지 갈 수 있으므로 컴퓨팅으로는 빠른 계산이 당연히 어렵다. 이 포스트에서는 이 문제를 무려 $O(N)$에 풀어볼 .. Dynamic Segment Tree and Lazy Propagation 이 포스트에서는 다이나믹 세그먼트 트리에 대한 소개와 레이지 프로퍼게이션까지 구현을 해보도록 한다. 엄청 큰 범위에서의 구간 쿼리? 다음 문제를 해결한다고 해보자. 수열 a가 있을 때 1. ai에 x를 더한다. 2. i > 1; auto lval = tree[tree[node].l].val; if (lval >= kth) return kth_query(tree[node].l, from, mid, kth); return kth_query(tree[node].r, mid + 1, to, int(kth - lval)); } Colored by Color Scripter cs 이 함수를 가지고 4번 쿼리를 처리하면 된다. 일기 예보를 해결하는 전체 코드는 다음처럼 짤 수 있다. 노드 개수를 주의하자. 1 2 3.. 세그먼트 트리로 직사각형 스위핑 feat. 3392 화성 지도 우리는 몇몇 문제를 통해 세그먼트 트리와 스위핑으로 직사각형의 면적 혹은 둘레를 구하는 방법을 알아볼 것이다. 대표적인 문제는 화성 지도가 되겠다. https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 스위핑 세그먼트 트리 소개 N개의 직사각형이 주어졌을 때 중복을 고려하여 총면적을 구하는 문제다. 바로 본론으로 들어가 우리는 두 개의 세그먼트 트리를 사용하겠다. 각 세그먼트 트리의 용.. 이전 1 2 3 4 ··· 6 다음
