돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/13209 문제 태그 더보기 Parametric Search 문제 소개 트리가 있다. 이중 k개의 간선을 끊어서 k+1개의 트리로 만든다. 이때 각 트리에 포함된 노드의 가중치의 합들 중 최댓값의 최솟값을 구하시오. 문제 풀이 트리의 간선을 '최대한 잘' 끊어야 한다. 트리별로 노드의 가중치의 합이 최대한 비슷하도록, 어느한쪽이 치우치지 않도록 끊어야 한다. 어떻게 해야 최대한 잘 끊을 수 있을까? 이를 생각하는 문제는 굉장히 어렵다. 너무 다양한 경우의 수가 나오게 된다. 따라서 좀 다른 방식을 생각해보자. 트리에서 어떻게 잘 잘라서 "가능한 최솟값"을 물어보는 문제이다. x가 된다면 당연히 x이상은 모두 다 가능하고, x가 불가능..

도입 다음과 같은 문제를 푼다고 생각해보자. 자동차 경주대회가 있었다. 먼저들어온 순서대로 N대의 자동차들에 대한 평균 속력이 주어진다. 하지만 이 차들중에 평균속력이 K이상인 차들은 우승자격이 박탈된다. 어떤 차가 우승하게 될까? 파라메트릭 서치란? 파라메트릭 서치(Parametric Search)는 기본적으로 이분탐색을 베이스로 깔고 들어간다. 나는 Parametric Search를 "조건내 최대(최소)를 찾는 문제를 log의 시간복잡도를 사용해 결정문제로 바꾸는 테크닉"이라고 말하고 싶다. 이 말만 들어서는 의미를 제대로 파악하기 힘들고 도입의 문제를 이용해 이 말을 풀어나가보려고 한다. 파라메트릭 서치의 역할 도입의 문제를 보면 K미만의 숫자 중 가장 큰 숫자를 찾는 문제가 된다. 하지만 Para..