블로그를 최근에 잘 하지 않았네요. 최근에 쓴 글 간단히 업로드합니다.

최근 jo_on님을 통해 알게 된 내용을 정리해 보았다. Theorem (Dilworth). Finite POSET \(P\)에 대해, \(P\)의 minimum chain cover의 크기는 \(P\)의 maximum antichain의 크기와 같다. 이 글에서는 Dilworth's theorem의 constructive pf를 목표로 한다. POSET과 Mirsky's theorem에 대해서는 전에 대충 써놓은 글이 있다. 1. Non-constructive proof \(\newcommand{\abs}[1]{| #1 |}\)가장 잘 알려져 있는 증명법이기도 하다. Construction과는 그다지 관계가 없으니 관심없다면 스킵해도 될 듯. \(P\)의 크기에 대해 귀납법을 사용하자. \(P\)의 m..

원본: https://codeforces.com/blog/entry/61205 Blogewoosh #1 - Codeforces codeforces.com Radewoosh의 블로그에 올라온 신기한 트릭을 리뷰한다. 해결해야 할 원본 문제는 여기서 볼 수 있다. https://szkopul.edu.pl/problemset/problem/wTy-sxQCIKry0Ml-6RvM0L78/site/?key=statement Zadanie Różne słowa (slo) - Problemset - SZKOpuł Congratulations, you solved it! The problemset isn't perfect, but we always aim to make it better. To do that we nee..

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

참고 : http://cubelover.tistory.com/21 Kitamasa법은 다음과 같이 계수가 결정된 선형 점화식을 갖는 수열의 \(n\)번째 항을 빠르게 결정할 수 있는 방법이다. $$ a_n = c_1 \cdot a_{n-1} + c_2 \cdot a_{n-2} + \cdots c_m \cdot a_{n-m} = \sum_{i=1}^{m}c_{i}a_{n-i} $$ Naive로 풀면 \(O(nm)\) 정도의 시간이 걸리고, $$ \color{red}{\begin{pmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-m+1} \end{pmatrix}} = \color{blue}{\begin{pmatrix} c_1 & c_2 & \cdots & c_{m} \\ & & ..

0. Introduction TSP는 가장 잘 알려진 NP - complete 문제 중 하나고, 문제 형태가 간단하기 때문에 다양한 variation이 존재한다. 오늘 다룰 것은 거리 공간(Metric) 위에서의 TSP인데, Metric TSP란 정점들을 어떤 거리 공간 \(X\) 위의 점으로 생각할 수 있고, 간선의 weight가 다음의 조건을 만족하는 거리 함수의 형태로 주어지는 TSP를 말한다. - \(d : X^2 \to \mathbb{R}\)- \(d(x,x) = 0 \)- \(d(x,y) = d(y,x) \)- \(\color{blue}{d(x,y)+d(y,z) \ge d(x,z)}\) (삼각부등식) 논의가 어렵게 느껴진다면, 그냥 2차원 평면 위에서 TSP 문제를 푼다고 생각해도 좋다. 안타..