구사과

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

알고리즘에서 다루는 많은 문제들은 그래프 문제로 환원할 수 있는데, 일반적인 그래프에서 어떤 문제들은 효율적으로 해결이 불가능한 경우가 있다. 이러한 비효율성의 대표적인 예시는 NP-hard로, 어떠한 문제가 NP-hard일 경우 다항 시간으로 푸는 것이 아예 불가능할 가능성이 높다. 그 외에도, 최단 경로 문제와 같이 다양한 쿼리에 대해서 빠른 시간 안에 해결하는 것이 어려운 경우 등, 비효율성의 예시는 NP-hard에 한정되지 않는다. 이러한 비효율성에 당착했을 때 자주 취하는 전략은 환원한 그래프의 특수성에 의존하는 것이다. 예를 들어, NP-hard 문제들이라 하더라도 그래프가 직선, 트리, 선인장, 이분 그래프일 때는 새로운 알고리즘적 기법들을 활용할 수 있다. 대표적인 패턴이자 이 글의 메인 ..

82등으로 본선 진출 실패했습니다. ucpc 예선 1등해서 기분 좋았는데 느슨했던 멘탈에 긴장감을.. 5번 이러면 될 거 같은데..? 옛날에 민컷 이야기라는 글도 썼고 나름 컷 문제는 잘 푼다고 생각했는데 아닌가.. 디닉도 팀노트 없이 짤 수 있는데... i -> j 로 가는 간선이 있으면 source -> i로 가중치 b의 유향 간선 잇고 i -> sink로 가중치 a의 유향 간선 잇고 i -> j로 가중치 c - a의 유향 간선 잇고 j -> i로 가중치 c - b의 유향 간선 잇고 그러면 (i, j) 가 모두 source쪽에 있으면 (주거) a의 비용 (i, j) 가 모두 sink쪽에 있으면 (업무) b의 비용 i가 source, j가 sink쪽에 있으면 (c-a) + a = c의 비용 i가 sin..

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

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 이라고 하는 새로운 플로우 알고리즘을 설명한다. 예전에 유량 관련 알고리즘을 정리할 때도 간략하게 설명한 적이 있는..