2017/06/14 썸네일형 리스트형 Parallel binary search 크루스칼의 공이라는 문제가 있다. 이 문제는 http://jason9319.tistory.com/280처럼 LCA를 이용하여 온라인 쿼리로 해결할 수 있으나 LCA를 쓰지않고 오프라인 쿼리로 해결 가능한 방법도 있다. Parallel binary search는 이 문제를 오프라인 쿼리로 해결해 줄 방법이다. 어떤 문제가 요구하는 정답이 단조 증가의 모양을 가질 때 binary search를 이용한 parametric search로 답을 구해줄 수 있다. 크루스칼의 공같이 답이 될 수 있는 수가 연속적이라면 우리는 쿼리 전체에 대하여 binary search를 수행하여 답을 구해낼 수 있다. 하지만 쿼리 하나씩 이분 탐색을 거칠경우 너무 많은 시간이 소요되기 때문에 쿼리를 모아놓고 한번 값을 구할 때 해당.. 더보기 Fenwick Tree(Binary Indexed Tree) http://jason9319.tistory.com/282 문제를 lazy progatition을 이용한 segment tree를 이용하다가 멘탈이 나가서 fenwick tree를 공부하였다. (https://www.acmicpc.net/board/view/15993) 펜윅트리는 BIT(Binary Indexed Tree)로도 불리며 갱신이 이루어지는 range의 구간 합 연산을 빠르게 해결해주는 자료구조로 알려져있다. 자료구조의 정당성과 시간복잡도등은 https://www.acmicpc.net/blog/view/21에 잘 설명이 되어있고 여기서는 간단하게 사용법만 알아보겠다. 123456789101112131415ll tree[MAX_N+1];void update(ll x, ll val) { while.. 더보기 BOJ)8217 유성 문제: icpc.me/8217 회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다. 각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다. 이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다. 따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자. 우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다... 더보기 BOJ)14434 놀이기구1 문제: icpc.me/14434 놀이기구를 타는 키 제한이 존재하고 각 날마다 키가 자라는 아이와 어떤 놀이기구를 타는지 물어보는 질의들이 주어질 때 각 날마다 아이들이 타는 놀이기구의 수를 출력하는 문제이다. 이 문제는 각 질의에 대하여 해당 놀이기구를 탈 수 있는 첫번 째 날을 구해주면 그 날 이후는 해당 놀이기구를 항상 탈 수 있으니 psum으로 해결 가능하다. 문제는 질의마다 첫번 째 놀이기구의 탑승 가능일을 구해주는 일이다. 우선 질의에 대해 첫번 째 놀이기구의 탑승 가능일을 탐색해야하므로 mid값을 날짜로 생각을 하자. 그럼 mid일에 놀이기구를 타야하는 두 아이의 키를 가져와야 하는데 이는 2차원 벡터로 각 아이에 대해 키가 크는 날짜를 벡터에 삽입해준다면 upper_bound로 계산해줄 수.. 더보기 이전 1 다음
