구사과

Splay tree 등의 BBST 구현을 여러번 시도해 보았지만 내가 대회에서 직접 짜면 버그가 너무 많아서 보통 피해왔었다. 얼마 전 QOJ를 읽다가 Weight-Balanced Tree라는 Persistent BBST의 굉장히 간단한 구현체를 찾아 이 블로그에 소개한다. 이 구현의 장점은:Rotate 연산을 사용하지 않는다.Rotate 연산은 유도하기 대단히 귀찮아서 보통 암기해야 하고 실수하기 쉽다.사실 이 구현도 Merge에서 암기해야 할 부분이 있는데 Rotate보단 쉬운 거 같다. 그리고 그 부분은 실수를 조금 해도 괜찮다.리프 노드만이 실제 원소에 대응된다. 리프 노드가 아니면 대응되는 원소는 없으며, 왼쪽 자식 / 오른쪽 자식을 모두 가진다. 일반적으로 우리가 사용하는 세그먼트 트리등과 동..

예전에 남부순환로 문제를 출제할 때 Mergeable heap에 관해서 사람들과 논의하던 때가 있었는데, Leftist heap / Randomized mergeable heap 모두 딱 와닿는 느낌의 논증은 없었던 것 같다. 최근에 Skew heap이라는 걸 접했는데 굉장히 짧고 아름다운 논증이 존재해서 소개한다. (아쉽게도 Worst-case bound가 아니라 남부순환로 문제에는 사용할 수 없다. 이론적으로는.)목표는 Merge 연산을 Amortized $O(\log n)$ 에 수행하는 것이다. 이것만 수행하면 Init, ExtractMin은 따라온다.두 트리를 머지할때 오른쪽 자식을 따라서 path를 타고 가자. 이 path를 따라 적힌 값들은 증가한다. 고로 이 path를 따라서 merge so..

(출처는 https://algorithmsoup.wordpress.com/2018/09/18/soviet-version-of-cantors-diagonalization-argument/ 이다.)소비에트 연방에는 무한히 많은 인민들이 있다.최근 공산당에 대해서 불만을 느낀 인민들은 지하조직을 결성하게 되었다. 그래서 모든 인민의 부분집합에 대해 이에 대응되는 지하조직이 생겼다. 이 중에는 공집합인 지하조직도 있고, 모든 인민을 포함하는 지하조직도 있다.지하조직은 국가에 불안정을 줄 수 있으니, 공산당은 이 문제를 "해결"하기 위해 모든 인민들에 대해 정확히 하나의 지하조직을 감시하게 시켰다. 각 인민들이 감시하는 지하조직은 서로 다르다.만약에 어떠한 인민이 자신이 속하는 지하조직을 감시하면 이 인민은 행복..