구사과

UCPC 2022에 사용했던 팀노트를 첨부한다. 기본적으로 예전 더불어민규당 팀노트를 기반으로 만들었는데, 당시랑 내가 지금 사용하는 코드베이스가 많이 달라서 내용은 꽤 많이 다른 것 같다. 당시에는 landscape 2-side로 만들어도 25장이 다 안 차서, 여백을 두더라도 가독성을 높이는 식으로 팀노트를 만들었는데. 이번에 저렇게 만드니까 50장이 넘게 나와서 도저히 진행할 수가 없었고, portrait / 2-side / 7pt 로 엄청나게 압축해서 넣었다. 2시간 정도 안에 급하게 만든 거라 여백 등등에서 부족한 점이 많으니, 실제 팀노트 구성 시에는 수정이 필요할 수 있다.

PA 2012. Mecze 두 선수가 경쟁하지 않았다는 것은, 두 선수가 항상 같은 팀에 있었다는 것과 동치입니다. 고로 각 선수가 무슨 팀에 있었는지를 크기 $M$ 의 배열에 저장하고, 배열들을 정렬한 후 중복 원소가 있는지를 체크하면 됩니다. 배열을 정렬하기 위해서는 배열간 비교가 가능한 vector 같은 자료형을 쓰거나 $M \le 50$ 이니 배열 대신 long long 자료형에 비트마스크로 저장하거나 등등의 방법이 있습니다. Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Build The Grid 사진으로 대체합니다: 이러한 구성을 찾는 방법은 여러 가지가 있습니다. 저의 경우에는 그냥 백트래킹을 돌려서 조건을 만족하는 그리드를 찍어보고, 규칙을 찾았습..

(2023.10.20 - Def2->Def3 증명의 오류를 수정하고 Typesetting을 좀 손봤다.) 알고리즘에서 다루는 많은 문제들은 그래프 문제로 환원할 수 있는데, 일반적인 그래프에서 어떤 문제들은 효율적으로 해결이 불가능한 경우가 있다. 이러한 비효율성의 대표적인 예시는 NP-hard로, 어떠한 문제가 NP-hard일 경우 다항 시간으로 푸는 것이 아예 불가능할 가능성이 높다. 그 외에도, 최단 경로 문제와 같이 다양한 쿼리에 대해서 빠른 시간 안에 해결하는 것이 어려운 경우 등, 비효율성의 예시는 NP-hard에 한정되지 않는다. 이러한 비효율성에 당착했을 때 자주 취하는 전략은 환원한 그래프의 특수성에 의존하는 것이다. 예를 들어, NP-hard 문제들이라 하더라도 그래프가 직선, 트리, ..

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 그 자체로는 실용적 가치가 존..

2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다.MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까 싶다. ..

Pisinger Algorithm Subset Sum 문제는, positive integer multiset S와 정수 t가 주어졌을 때, 합이 t인 S의 부분집합이 있는지를 찾는 문제이다. S의 원소 범위가 1 이상 M 이하의 정수라고 가정하자. $M$ 에 대한 dependency가 없이 풀려면 당연히 NP-hard이다. 그냥 DP를 하면 $O(n^2M)$ 이다. 각 숫자를 prefix sum으로 처리하면 $O(nM^2)$이다. Generating function으로 $O(nM \log nM)$ 에 푸는 풀이가 비교적 최근에 발견되었다. 꽤 깔끔한 $O(nM)$ 풀이를 서술 일단 첫 번째 Lemma는, 이 문제를 모든 수가 [-M, M] 인 multiset S에서 합이 1 = F[j][k + a[i]]..

그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을 사용한다. 이 알고리즘의 특징은 빈 그래프에서 시작해서 유량을 증가시키는 "증가 경로" 를 찾는 것을 반복하는 식으로 작동한다는 것이다. Dinic 알고리즘은 최악의 경우 $O(V^2E)$ 에 작동하지만 실제로는 이보다 훨씬 효율적으로 작동한다. 하지만 그럼에도 선형 시간에 가까울 정도로 빠르지는 않고, 한계가 분명히 있는 알고리즘이다. 이 글에서는 Push-relabel 이라고 하는 새로운 플로우 알고리즘을 설명한다. 예전에 유량 관련 알고리즘을 정리할 때도 간략하게 설명한 적이 있는..

1. Introduction MapReduce 라는 프로그래밍 프레임워크는 대용량의 데이터를 처리하는 데 있어서 높은 성능을 보여주고, Apache Hadoop과 같은 오픈 소스 구현체들을 통해서 실용적으로도 그 가치를 증명하였다. 이 글에서는 그래프 최적화 문제를 푸는 데 효과적인 방법 중 하나인 Primal-Dual Method를 MapReduce 프레임워크에서 적용하는 새로운 프레임워크를 소개하고, 이를 통해서 Densest Subgraph Problem의 Near-linear time algorithm을 얻고자 한다. 정확히는, 이 글에서는 $O(\frac{\log n}{\epsilon^2})$ 번의 MapReduce iteration을 통하여 Densest Subgraph problem의 $(1..

Algorithmic Engagements 2010. Rectangles 2 부분 직사각형의 크기가 $w \times h$ 라면, 그 둘레는 $2(w+h)$ 이고, 등장 횟수는 $(n-w+1)(m-h+1)$ 입니다. 이를 토대로 모든 가능한 경우를 나열한 후 횟수를 합해주면 됩니다. Algorithmic Engagements 2010. Coins 문자열을 수열로 변환합니다. 앞면에 대해서는 $1$ 을, 뒷면에 대해서는 $-k$ 를 적어줍시다. 이렇게 하면, 구간의 합이 $0$ 인 것과 앞면의 수가 뒷면의 수보다 $k$ 배 많이 나온 것이 동치입니다. 고로 구간 합이 0인 가장 긴 구간을 찾아야 합니다. 위 수열의 부분합 $S[i] = \sum_{i = 1}^{n} A[i]$ 를 구해줍시다. 이제 답은 $..