구사과

BOJ 33365. Password최댓값은 $n$ 입니다. 최솟값은, 비밀번호의 중앙에 비알파벳 문자를 배정한 후, 중앙에서 왼쪽 / 오른쪽으로 세 문자마다 비알파벳 문자를 배정하면 됩니다.BOJ 33324. The Romanian Sieve$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 을 $O(\sqrt n)$ 시간에 계산할 수 있으면 전체 문제를 이분 탐색으로 $O(\sqrt n \log n)$ 시간에 해결할 수 있습니다. 그 방법을 소개합니다.$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 를 계산할 때는, 항상 $\lfloor \frac{n}{i} \rfloor \leq \sqrt n$ 혹은 $i \leq \sqrt n$ 중 하..

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데$|f(x)| \leq g(k)$$Decision(x) = Decision(f(x))$같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:$n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance..

보호되어 있는 글입니다.