원본 Codeforces 블로그 문제를 잘 푸는 사람일수록 알고리즘을 암기하기보단 끊임없이 고찰하고, 최적화하고, 예외를 효과적으로 비껴가는 방법을 연구하는 것 같다. 그런 의미에서 이 포스팅 작성자도 굉장히 존경스럽다. 세상은 넓고 갓갓은 많아..MO's algorithm 흔히 루트질로 불리는 MO's algorithm은 배열에 대한 구간 쿼리를 오프라인으로 처리하는 많은 문제를 아슬아슬한 복잡도로 해결할 수 있게 해주는 트릭이다. kesakiyo님의 친절한 introduction 끄흐수님의 깔끔한 introduction MO's algorithm으로 문제를 풀기 위해서는 다음이 성립해야 한다 : - 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s-1, e] 또는 [s, e+1]에 대한 ..

화학과지만 어제 풀어본 심층 문제가 꽤 재미있어서 공유하기로 했다. Statement. 두 점 \((0,1),(1,0)\)을 지나고, \([0,1]\)에서 연속이며 \((0,1)\)에서 두 번 미분가능한 감소함수 \(f\)가 있다.\(y = f(x)\)의 그래프를 \(x\)축으로 회전한 부피와 \(y\)축으로 회전한 부피가 같을 때, 다음 물음에 답하시오. 단, 모든 적분은 \(0\)에서 \(1\)까지의 정적분이다. (1) \(\int \left(f - x\right)^2 dx \)를 구하시오.(2) \(\int f - f^2 dx \)가 최대가 되는 \(f(x)\)를 구하시오.This section is intentionally left blank. Hint : 1번은 간단하다. \(f(x)\)를 미리..

원본은 여기. 다음을 만족하는 연속함수 \(f\)는 존재하지 않음을 보여라. $$ f(0) = 1, \forall n \in \mathbb{Z}_{0} \int_{0}^{1} x^{n} f(x) dx = 0$$ 사실 고등학교 수학만으로는 어렵다. 다음의 정리를 받아들이자. Weierstrass Approximation Theorem : 구간 \(I = [a,b]\)에서 연속인 함수 \(f\)에 대해, \(f\)에 '평등근사'하는 다항식 \(P(x)\)가 존재한다; i.e. 임의의 실수 \(\epsilon>0\)에 대해, 모든 \(x\in I\)에 대해 \(|f(x) - P(x)| < \epsilon\)이도록 하는 다항식 \(P(x)\)가 존재한다. 이제 그리 어렵지 않은 문제로 바뀐다.임의의 \(\eps..

\(a, b, c, d \in [0,1]\)이다.\(abcd \le \frac{4}{27}\) 또는 \((1-a^2)(1-b^2)(1-c^2)(1-d^2) \le \frac{4}{27}\)임을 보여라. \(x = \sqrt{ab}, y = \sqrt{cd}\)라고 두자. \((1-a^2)(1-b^2) = (1-a^2-b^2+(ab)^2) \le 1 - 2ab + (ab)^2 = (1-x^2)^2\)이다.그래서 \((1-a^2)(1-b^2)(1-c^2)(1-d^2) \le (1-x^2)^{2}(1-y^2)^{2} \le (1-xy)^4\)이다.\(abcd \le (xy)^{2}\)이므로 결국 \(xy \ge \sqrt{\frac{4}{27}}\)일 때 \((1-xy)^4 \le \frac{4}{27}\)임..

Mirsky's theorem은 POSET에 관련된 기초적인(?) 정리 중 하나인데, 어디 심층 문제에 대뜸 나왔다길래 포스팅해본다.이에 완전히 대응되는 정리로 Dilworth's theorem이 있지만 증명이 복잡해서 일단은 Mirsky만 증명하기로 한다. POSET(PreOrder SET)의 형식적인 정의는 다음과 같다. 직관적으로는 두 정수 간의 약배수 관계를 생각하면 된다. - 집합 \(P\)의 원소들에 대해서, 관계 \(\preccurlyeq\)가 다음을 만족한다.- 반사율 (reflexivity) : 임의의 \(a \in P\)에 대해 \(a \preccurlyeq a\).- 추이율 (transitivity) : \(a, b, c \in P\)에 대해 \(a \preccurlyeq b \ \w..

문제를 다 푼 사람의 후기는 여기서 볼 수 있다.요즘 실패 후기만 쓰는 것 같아서 기분이 별로다. 서울대랑 카이스트는 잘 봐야지! 문제 요약 : 1. 사골이 되어버린 유형의 확통 문제다. [1-1] \(A \cup B \cup C = \{1, \ldots , 6\}\)이고, \(|A \cap B| = 2, |B \cap C| = 1\)일 때, 가능한 \((A,B,C)\)의 개수를 구하여라. [1-2] \(D \cup E = \{7,8,9\}\)이고, \(|D| > |E| \ge 1\)인 \((D,E)\)의 개수를 구하여라. 2. 함정에 빠지기 쉽다. 하지만 함정에 빠지지 않는다면 간단히 풀리는 문제다. (난 못풀었다 ㅎ) 다음을 만족하는 \([0,1]\)에서 연속인 함수 \(f\)가 존재하는가?$$ f(..