본문 바로가기

parallel binary search

Parallel binary search 크루스칼의 공이라는 문제가 있다. 이 문제는 http://jason9319.tistory.com/280처럼 LCA를 이용하여 온라인 쿼리로 해결할 수 있으나 LCA를 쓰지않고 오프라인 쿼리로 해결 가능한 방법도 있다. Parallel binary search는 이 문제를 오프라인 쿼리로 해결해 줄 방법이다. 어떤 문제가 요구하는 정답이 단조 증가의 모양을 가질 때 binary search를 이용한 parametric search로 답을 구해줄 수 있다. 크루스칼의 공같이 답이 될 수 있는 수가 연속적이라면 우리는 쿼리 전체에 대하여 binary search를 수행하여 답을 구해낼 수 있다. 하지만 쿼리 하나씩 이분 탐색을 거칠경우 너무 많은 시간이 소요되기 때문에 쿼리를 모아놓고 한번 값을 구할 때 해당.. 더보기
BOJ)8217 유성 문제: icpc.me/8217 회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다. 각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다. 이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다. 따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자. 우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다... 더보기