구사과

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

2021.??.?? problem solving이라고 적혀 있는 글이었습니다. 정확히 이 때 이 글을 왜 적었는지는 기억이 안 납니다. 당시에 문제를 몇개 더 풀어서 다른 글과 함께 올리려고 했었는데, 많이 미뤄지기도 했고, 그 문제들은 따로 올리는 게 좋을 것 같아서 그냥 올립니다. 9월까지 알고리즘 글이 최소 5개는 더 올라올 것으로 예상됩니다.AMPPZ 2019 C. Polygon수열 $a_1, a_2, \ldots, a_n$ 을 가지고 볼록 다각형을 만들 수 있을 조건은, 가장 긴 변을 제외한 변들의 길이 합이 가장 긴 변보다 길면 됩니다. 수열을 정렬한 후, 가장 긴 변을 $i$ 번이라고 합시다. 그보다 작은 변들은 합만 특정 수 이상이 되면 되니까, 그냥 전부 골라주면 됩니다. 고로 $1 \l..

Part 1. Uniform SamplingGiven an undirected unweighted graph $G = (V, E)$, A $(1 \pm \epsilon)$ cut sparsifier $H = (V, F, w)$ satisfies the following:$F \subseteq E$For all $\emptyset \subsetneq S \subsetneq V$ it holds that $\delta_w(H, S) \in [(1 - \epsilon)\delta_{\mathbf{1}}(G, S),(1 + \epsilon)\delta_{\mathbf{1}}(G, S)]$This is a sparsification that preserves the cuts. Compare this to the ..