구사과

(6/23 01:20: 7월 과외 마감하였습니다. 많은 성원에 진심으로 감사드립니다.) 안녕하세요. 구재현입니다. 학교 복학을 위해서 최근에 회사를 그만 두었는데, 2달 정도 여유 시간이 있어서 그동안 알고리즘 과외를 진행해 볼까 합니다. 프로필 글 작성 시간 기준으로 변동이 있을 수 있습니다. BOJ: koosaga (Rank 1, 11310 solved) solved.ac: koosaga (Rank 1, Master, 3255) Codeforces: ko_osaga (World Rank 13. Korea Rank 1, Legendary Grandmaster, 3315) Google Code Jam World Finals 2회 출전 (2021, 2020) Facebook Hacker Cup World ..

https://epubs.siam.org/doi/epdf/10.1137/1.9781611973099.139 Andreas Bjorklund는 그래프 이론에 대수적 방법을 접목시켜서 50년짜리 SOTA를 여럿 깬 것으로 유명하다. 최근에 논문 중 하나를 읽어볼 기회가 생겼는데 생각보다 훨씬 elementary한 방법이라서 놀랐다. 간단하게 요약하면 좋을 것 같아서 짧은 노트를 써 본다. 문제는 "그래프가 있고 K개의 정점이 마크되어 있을 때 이 정점들을 모두 지나는 최소 길이 simple cycle을 찾는 문제" 이고, 시간 복잡도 aim은 $O(2^k poly(N))$ 이다. 풀이는 다음과 같다. 먼저 찾을 사이클의 시작점을 $k$ 개 중 하나로 고정하자. 다음과 같은 walk $w = \{s, v_1,..

일반적인 그래프에서 효율적으로 해결할 수 있는 문제들을, 간선이 추가되고 제거되는 등의 업데이트가 가해질 때도 효율적으로 해결할 수 있는지를 연구하는 분야를 Dynamic Graph Algorithm이라고 부른다. 이 분야에 대해서는 최근 많은 연구가 진행되고 있으며, 여러 차례의 멤버십 글로도 이 분야의 다양한 최신 기술과 테크닉을 소개한 바 있다. 이 글에서 소개할 주제는 Decremental Graph Algorithm을 얻을 수 있는 프레임워크 중 하나인 Congestion Balancing 이다. 어떠한 알고리즘이 decremental하다는 것은, 간선 추가 쿼리는 처리할 수 없으나 제거 쿼리는 처리할 수 있다는 것을 뜻한다. Decremental algorithm 그 자체로는 실용적 가치가 존..