구사과

다음과 같은 문제를 생각해 보자.크기 N의 수열이 있을 때, 길이 K 이상인 구간 중 최대 평균을 계산하라. 식을 전개해 보자. 주어진 입력의 부분합을 Si 라고 하면, j - i >= K 일 때 (Sj - Si) / (j - i) 를 최대화해야 한다. 하지만 그렇게 쉬워 보이지 않는다. 어떻게 해야 할까?1. 답에 대한 이진 탐색어떠한 문제의 가능한 최대 / 최솟값을 계산하기 위해서, 문제를 결정 문제로 바꿔서 이진 탐색을 하는 방법이 잘 알려져 있다. 예를 들면, "가능한 답 중 최댓값을 계산하라" 는 문제를, "X 이상이 이 문제에서 가능한 답인지를 판단하라"는 문제로 바꾸면, 가능한 답 중 최대인 X를 이진 탐색으로 판별할 수 있다. 만약에 최댓값을 계산하는 것은 어렵지만, X 이상이 가능한 답인..

https://www.acmicpc.net/problem/8128증명에 증명을 더해가면서 시간 복잡도를 줄이는 스타일의 그리디였는데 재밌었다. 일단 먼저 N^2 알고리즘을 목표로 시작해보자. 가장 많은 역을 덮는 지하철 노선의 집합을 최적 집합이라고 한다. Lemma 1. 최적 집합의 모든 끝점을 리프로 변형시킬 수 있다.증명 : 그렇지 않은 최적 집합이 존재한다면 이를 두고 생각해 보자. 만약에 현재 끝점이 리프가 아니면, degree가 2 이상이라 빠져나갈 구멍이 하나 존재한다. 이 구멍으로 경로의 길이를 증가시켜나가면 답을 감소시키지 않으면서 한쪽을 리프로 만들어 줄 수 있다. Lemma 2. 최적 집합에 덮인 지하철역이 서브트리를 이루게 변형시킬 수 있다. (이 때 서브트리는 subgraph로써의..