-
Maximum Matching in General Graph
Maximum matching algorithm of “General graph” 그래프에서 matching은 인접해있는 정점쌍을 중복되지 않게 선택한 것들의 집합이며, maximum matching은 이 집합 중 가장 크기가 큰 것을 구하는 문제이다. 이와 관련하여 만약 그래프가 bipartite라면 보다 간편하게 풀 수 있으며, 이 알고리즘은 잘 알려져있다. 하지만 일반적인 그래프에서 찾는 알고리즘은 보다 복잡하여 CP에서 잘 다루지 않는 내용이다. 그래서 이번에는 잘 알려지지 않은 그래프 최대 매칭에 대한 알고리즘을 소개해보려 한다. 여기서는 일반적인 그래프에서 최대 매칭을 구하는 알고리즘 중 Blossom algorithm에 대해...
-
Singular Elliptic Curves
서론 최근 타원 곡선에 대해서 공부하면서 피상적으로 이해하던 부분을 좀 더 깊이 이해하는 단계에 들어서고 있습니다. 특히 수학에 대해서 배우는 것은 좋아하지만 고등 수학 위로 배운 것이 없어, 많은 재미를 느끼고 있습니다. 그러면서 해소된 궁금점은 바로 “Discriminant가 왜 0이면 안 되는 것일까?” 였습니다. 타원 곡선에 대한 Wikipedia article 을 살펴보면, $y^2 = x^3 + ax + b$ 꼴의 short Weierstrass equation에 대해서 Discriminant $\Delta = -16(4a^3 + 27b^2)$ 가 0이 아니여야 한다는 조건을 달고 있습니다....
-
FPT Inapproximability of Directed Multicut
FPT Inapproximability of Directed Multicut 그래프의 연결성, 그리고 연결성을 변화시키는 방법 (그래프 절단) 은 알고리즘 연구의 극초창기부터 연구되었던 문제들이다. 그래프 절단은 냉전 초기 공중폭격으로 적국의 철도망을 파괴하는 군사적인 목적으로 연구가 시작되었다. 이후 반세기 이상 이러한 류의 문제는 그래프에 대한 최적화 문제 중 가장 기초적인 문제로 자리잡는다. 이 문제는 이론적으로도 다른 문제의 근간이 되며, 무수히 많은 현실적 계산 문제와 연관되어 있다. 그래프 절단 유형의 문제로는 크게 다음과 같은 4가지 종류가 있다. 이하 특정한 언급 없을 시,...
-
루트로 문제 뚫기
서론 수준급의 알고리즘 문제를 풀다 보면 다양한 장벽에 가로막히곤 합니다. 어려운 문제들 중에는 특히 쿼리형1의 문제가 많은데, 이런 문제들은 단순한 방법으로 답을 도출해내는 것은 쉽지만 시간 복잡도를 줄이는 데에 복잡한 자료구조가 요구되어 난이도가 매우 높아지는 경우가 많습니다. 이러한 문제들의 의도는 주로 특수한 형태의 트리2나 이분 탐색 등을 활용하여 $O(Q\log^K{N})$ 꼴의 시간 복잡도를 만들어내도록 하는 것이지만, 일부 문제의 경우 $O((N+Q)\sqrt{N})$과 같이 루트가 시간 복잡도에 포함되는 것이 정해인 경우도 있습니다. 대표적인 것이 이전에 소개한 바 있는 Mo’s...
-
프로그램의 메모리 사용량 측정 방법
안녕하세요? 오늘은 프로그램의 메모리 사용량을 측정할 수 있는 방법에 대해 알아보았습니다. 아래 코드들은 최적화 방지를 위해 -O0 옵션으로 컴파일 후 실행되었습니다. Indroduction 보통 온라인 저지 시스템에서의 채점 결과 중에는, MLT(Memory Limit Exceeded)가 포함되어 있습니다. 문제에서 주어진 메모리 제한을 초과할 경우 이러한 메시지가 뜨게 됩니다. 사실 대부분의 문제에서는 메모리를 꽤 넉넉하게 주기 때문에, 메모리 제한 초과는 특수한 상황이 아니라면 그리 자주 발생하는 편은 아닙니다. 재귀함수가 계속해서 호출된다거나, 큐가 계속 커진다거나 하는 상황에서 그나마 자주 발생하는 편이고,...