-
AtCoder Regular Contest 075 C Meaningful Mean 풀이
문제 요약 문제 링크 $N$개의 수가 있다. $i$번째 수를 $a_i$라 하자. 수열 $a$의 $N$개의 수에서 연속한 수들을 고르는 방법의 가지수는 $\frac{N \times (N+1)}{2}$ 개이다. $\frac{N \times (N+1)}{2}$ 개 중에서 평균이 $K$ 이상인 것이 몇개인지 구하라. $ 1 \le N \le 2 \times 10^5, 1 \le K \le 10^9, 1 \le a_i \le 10^9 $ 풀이 1. $O(N^3)$ Naive 한 방법. $\frac{N \times (N+1)}{2}$ 개의 모든 경우에 대해서, 직접 합을 구하고 평균이 $K$ 이상인지를 확인한다. 2....
-
N! mod P 의 빠른 계산
서론 $N!$ 은 1이상 $N$ 이하의 모든 정수를 곱한 수 이다. 이 $N!$는 다양한 조합론적 상황에서 많이 사용된다. 이 $N!$을 특정한 소수 $P$로 나눈 나머지를 빠르게 ($O(\sqrt{N} \log{N})$ 시간에) 계산 하는 방법에 대해서 알아본다. Naive 팩토리얼을 구하는 가장 쉬운 방법은 모든 1이상 $N$ 이하의 수를 곱해서 $P$ 로 나누는 것이다. $ab$를 $P$로 나눈 나머지와 $(a \bmod P)(b \bmod P) \bmod P$ 가 같다는 것을 이용하면, 사이에 나오는 숫자를 항상 $P^2$ 이하로 유지하면서 쉽게 구할 수...
-
Half Plane Intersection
소개 안녕하세요. 이번 글에서는 반평면 교집합(Half Plane Intersection)에 대해 소개해드리려고 합니다. 반평면 교집합으로 풀 수 있는 몇 가지 재미있는 문제들이 있는데, 생각보다 관련 자료가 많지 않아서 간단하게나마 정리해 보았습니다. Half Plane Intersection 반평면(Half Plane)이란, 평면 상에 하나의 직선을 그었을 때 나누어지는 각각의 영역을 말합니다. 반평면들이 여러 개 모이면 그 교집합의 형태는 아래와 같이 볼록 다각형(convex hull)이 됩니다. 그럼 대체 이 교집합을 알면 어디에 써먹을 수 있을까요? 후술하겠지만 대표적으로는 볼록 다각형의 내접원을 구하는 데 활용할 수...
-
Codeforces Round #578 개최 후기
개요 Codeforces Round #578 (Div. 2) Announcement Editorial 지난 8월 11일, 현재 세계 최대 규모의 사설 프로그래밍 대회 사이트인 Codeforces에서 hyunuk (aka. jwvg0425) 님과 제가 공동 개최한 Codeforces Round #578 (Div. 2)가 열렸습니다. 이전까지 소규모 대회 개최에 출제자나 검수자로 참여해보기는 했었으나, 백 명 내외가 참가했던 기존 대회들과는 달리 무려 만 명이 넘게1, 그것도 전세계에서 참가하는 대회였기에 본격적이었습니다. 이 글에서는 이 라운드가 개최되기까지의 전 과정을 돌이켜보며 생각을 서술하고, 문제별로 간단한 솔루션과 함께 코멘트를 남겨보려고 합니다. 역사...
-
$O(N^{1/4 + ε})$ 시간 복잡도에 소인수 분해하기
$O(N^{1/4 + \epsilon})$ 시간 복잡도에 소인수 분해하기 소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 “어려운” 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다...