구사과

예전에 남부순환로 문제를 출제할 때 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/ 이다.)소비에트 연방에는 무한히 많은 인민들이 있다.최근 공산당에 대해서 불만을 느낀 인민들은 지하조직을 결성하게 되었다. 그래서 모든 인민의 부분집합에 대해 이에 대응되는 지하조직이 생겼다. 이 중에는 공집합인 지하조직도 있고, 모든 인민을 포함하는 지하조직도 있다.지하조직은 국가에 불안정을 줄 수 있으니, 공산당은 이 문제를 "해결"하기 위해 모든 인민들에 대해 정확히 하나의 지하조직을 감시하게 시켰다. 각 인민들이 감시하는 지하조직은 서로 다르다.만약에 어떠한 인민이 자신이 속하는 지하조직을 감시하면 이 인민은 행복..

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 ..

Given 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 distance spanner, which ..

Day 3 Mississippi River 미네아폴리스 근처에서 일어났다. 전날과는 달리 잘 잤고, 상쾌하게 일어났다. 시애틀을 떠난 후 처음 보는 대도시였고, 여행이 끝나간다는 실감이 나게 했다. 아침은 전날 점심 식사를 같이 한 미네소타 할머니와 LA에서 오신 노부부 분들과 함께했다. 노부부 분들은 LA에서 시애틀, 시애틀에서 시카고, 시카고에서 뉴올리언즈로 가는 기차를 연달아 타시는 것 같았다. 태평양 연안과 미시시피 강을 종주하는 코스로, 기차로만 해도 일주일 정도가 걸리는 코스이다. 기차는 세인트 폴 - 미네아폴리스에서 30분 이상 길게 정차한다. 창밖으로 미시시피 강이 쏟아지는 멋진 풍경의 역이었다. 밖에 나가서 더 좋은 사진을 찍고 싶었으나, 기차 밖으로 나가면 기차가 강을 가리고 있어서 (..

Day 2 Western Montana - Near Glacier National Park 6시 반 좀 넘어서 일어났다. 잠은 그런대로 잤지만, 썩 개운치는 못하게 일어났다. 창문을 열어보니.. 어제 오후와는 완전히 다른, 그림같은 설원 속에 있었다. (사진은 그림같이 않음에 양해를 부탁한다. 동영상으로 찍은 경우가 많아 그렇다) 아직 진짜는 시작도 안 했으니, 바로 아침을 먹으러 간다. 아침도 몇 가지 옵션을 선택할 수 있다. 나는 스크램블 에그로 골랐다. 아침을 같이 먹었던 대학생은 캐나다에 있는 집으로 가기 위해 기차를 탔다고 했다. 보통은 집에 갈때 6~7시간 정도 운전해서 가는데, 지금은 고속도로가 빙판이 되어 있을 것 같아서 기차로 간 후 역에서 부모님이 픽업해주시기로 했다고. 기차가 미국의 ..

정말 갑작스럽지만, 저번 주 3주 전 6주 전 (...) 암트랙의 Empire Builder를 타본 후기를 써 보려고 한다. 3월 6일 ~ 3월 8일은 공휴일이 끼어 있는 주도 아니고 아무 일도 없는 시기지만, 과제가 없길래 2주 전쯤에 충동적으로 티켓을 구매했다. 보스턴 → 시애틀 비행기, Empire Builder, 시카고 호텔 1박, 시카고 → 보스턴 비행기 표를 끊고, 평소처럼 살다가 전날 최소한의 준비물만 챙겨 출발했다. Day 1 Seattle 4시 반 기상 후 Boston Logan에서 6시 50분 비행기를 타고 시애틀로 갔다. 비행 시간은 약 6시간 정도로, 시차 때문에 3시간이 당겨져서 도착 시간은 10시였다. 몇천 km를 넘어서 Pacific에 왔다는 실감은 그다지 들지 않았다. 날씨가..

Undirected graph $G = (V, E)$ 에 대해, $G$의 $t$-spanner $H = Spanner(G,t) = (V, E^\prime)$ 는 다음 성질을 만족한다: $E^\prime \subseteq E$ 모든 $u, v \in V$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작음 즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다. $E^\prime \subseteq E$ 모든 $(u, v) \in E$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작..

Even-Shiloach Algorithm은 Unweighted directed graph $G = (V, E)$ 에 대해서 incremental / decremental SSSP를 빠르게 해결하는 알고리즘이다. Naive하게는 매번 BFS를 해서 $O(m^2)$ 시간에 해결할 수 있는데, 이 알고리즘을 사용하면 이를 $O(nm)$ 으로 최적화할 수 있다. $O(m^2)$ 에 비해서 엄청나게 효율적이진 않지만 분명히 nontrivial한 bound이고, 내가 아는 state-of-the-art method는 전부 다 Near-linear가 아니라 $O(nm)$ 에 훨씬 가까운 바운드이다. 그것도 복잡한 알고리즘들이 대다수. 이 글에서는 원래 Even-Shiloach Algorithm보다 강한 statem..