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

최근 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]에 대한 ..

PS를 하면서 Persistent라는 단어가 붙는 자료구조는 Persistent Segment Tree 외에는 보기 힘들지만, 사실 Persistent라는 prefix는 꽤나 일반적인 의미를 지닌다. 어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 그 자료구조를 'Persistent하다'고 한다. 조금 더 세부적으로 분류하면, 이전의 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하지만 최종 상태를 제외하면 모두 read - only라면 Partially persistent 혹은 Confluently persistent라고 한다. 분류는 거창하지만 구현이 그렇게 난해한 건 아니다. 일반적인 방법론은 Fat node, Path co..

아직 공부중인 자료구조 / 알고리즘들이다.세상에 똑똑한 사람이 너무 많아.. 1. DP tricks 1.1. Alien Trick (Wang Qing-Shi Binary Search) 구사과 블로그imeimi 블로그원문을 구할 수 있는 곳 (중국어) IOI 2016 AliensNAIPC 2017 Blazing new trails 1.2. dynamic CHT (without pointer) 일명 성적CHT. 본지가 언제인데 아직도 못 짜냐 ㅡㅡ 1.3 Li-Chao tree Doc2 csacademy 연습문제 1.4. Knuth Optimization with rigorous proof 2. Offline Dynamic Tricks 2.1. Offline Dynamic Connectivity 2.2. D..