구사과

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

알고리즘 하시던 분들을 현실에서 만나게 되면 자주 듣는 질문이 "왜 ID가 구사과인가" 라는 질문이다. PS를 시작한 것은 고등학교 때지만 "컴덕후" 로 살던 초등학생 시절이 있었다. 2008년 집에서 새로 산 (보급형) 컴퓨터에 윈도우 비스타가 깔려 있었는데, 잘 알려졌다시피 비스타는 새 컴퓨터에서 돌리기에도 조금 많이 느렸다. 이 문제를 해결하기 위해 유출된 윈도우 7 비공개 베타를 주워서 설치했고, 신세계가 열렸다. 컴덕후 생활의 시작이었다. 시간이 지났고 그때 활동하던 커뮤니티에서 윈도우 8에 대한 이야기가 돌기 시작했다. "플랫 UI" 라는 미명하에 등장한 추태는 초등학생인 나에게 큰 상처를 남겼다. 이것이 미래라면 나는 도망치겠다고, 2달 동안 밥만 먹고 컴퓨터를 붙잡은 끝에 OS X Snow..