-
Polya's Enumeration Theorem을 이용한 카운팅 문제 해결
개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...
-
카운팅 테크닉
개요 AtCoder에서 문제를 풀다 보면 백준 온라인 저지나 한국의 대학생 대회에서와 다르게 경우의 수, 기댓값, 확률을 묻는 조합론 문제들이 더 자주 등장한다는 사실을 관찰할 수 있습니다. 한 대회에 출제된 문제 절반 이상에서 $\pmod{998244353}$이 등장해서 너무 과하다고 느껴질 때도 있을 정도입니다. 이 글에서는 제가 문제를 풀면서 자주 보았던 유형들을 몇 가지 선정해서 소개해 보려고 합니다. 각 유형마다 이를 해결하는 테크닉을 소개(널리 통용되는 이름이 없다면 적당히 이름을 붙였습니다)하고, 연습 문제로 AtCoder Regular Contest에서 등장했던 문제를 2개씩 선정했습니다....
-
The Short-Side Advantage in Random Matching Markets
이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의...
-
Combinatorial Nullstellensatz
1. 서론 그래프와 같은 여러 조합적인 대상의 수학적 성질은 이론 전산학 등의 분야에서 여러 방향으로 응용될 수 있다. Combinatorial Nullstellensatz는 그래프를 포함한 여러 조합적인 대상의 성질을 증명하는데에 응용될 수 있다. 이 글에서는 Combinatorial Nullstellensatz을 증명하고, 이후 여러 조합적인 대상에 이를 적용해본다. 2. Combinatorial Nullstellensatz Theorem. (Combinatorial Nullstellensatz) 체 $\mathbb{F}$와 다항식 $f \in \mathbb{F}[x_1, x_2, \cdots, x_n]$ 이 있다고 하자. $\deg(f) = d = \sum_{i=1}^n d_i$ 이고, $\prod_{i=1}^n x_i^{d_i} \neq 0$ 라면, $\lvert L_i \rvert >...
-
라틴 직사각형과 홀의 결혼 정리
라틴 방진과 스도쿠 라틴 방진 (Latin Square)은 서로 다른 $n$가지 기호로 구성되며, 각 행과 열에 $n$가지 기호가 모두 한 번씩 등장하게 만든 $n\times n$ 행렬입니다. 편의를 위해 $n$가지 기호 대신 $1$부터 $n$까지의 수 배열이라고 생각합시다. 라틴 방진을 만드는 방법은 여러 가지가 있는데, 가장 간단하게 생각할 수 있는 방법은 다음과 같습니다. 첫 번째 행에 $1$부터 $n$까지의 수를 순서대로 적는다. $k$번째 행에는 $k-1$번째 행을 왼쪽으로 한 칸 회전한 배열을 적는다. $(2 ≤ k ≤ n)$ 왼쪽으로 한...
-
Faster Exponential Algorithm for Permutation Pattern Matching
Introduction “스택 수열”이라는 간단한 문제를 생각해 봅시다. https://www.acmicpc.net/problem/1874 이 문제는 스택을 이용한 시뮬레이션으로 해결할 수 있습니다. 요약하면, $[n] := {1, \cdots, n}$의 순열 $\sigma _ {1}, \cdots, \sigma _ {n}$이 주어졌을 때, $1, \cdots, n$을 순서대로 스택에 push(+)했다가 pop(-)하여 $\sigma _ {1}, \cdots, \sigma _ {n}$을 만들 수 있는지를 판별하는 문제입니다. 반대로 $\sigma _ {1}, \cdots, \sigma _ {n}$을 push-pop하여 $1, \cdots, n$으로 정렬할 수 있는지를 묻기도 하는데요, 이 경우에 $\sigma$를 stack-sortable permutation이라고 합니다. “스택...
-
Integer Partition
개요 고등학교 교육과정의 확률과 통계 과목에서도 볼 수 있었던 자연수의 분할은 DP로 계산할 수 있어서 PS에서도 종종 등장하는 주제입니다. 이 글에서는 자연수 분할의 점화식과 빠르게 계산하는 방법, 그리고 문제풀이에서의 활용을 다룹니다. 자연수 $n$을 자연수 $k$개의 합으로 나타내는 방법의 수를 $P(n,k)$라고 합시다. 자연수 $n$을 분할하는 방법의 수를 $P(n)=\sum_{k=1}^{n}P(n,k)$이라 합시다. 예를 들어, 4를 분할하는 방법의 수는 위 그림처럼 5가지가 됩니다. $P(n,k)$를 $O(nk)$에 계산하는 방법 $P(n,k)$를 직접 구하는 간단한 공식은 알려져 있지 않고, 보통 점화식을 통해 계산합니다. 위...
-
Prüfer sequence
소개 안녕하세요. 이번 글에서는 labeled tree를 unique한 수열로 나타내는 Prüfer sequence에 대해 소개해드리려고 합니다. 사실 문제 풀이에 많이 활용되는 개념은 아니지만, 이해하기 쉬우면서도 이를 적용해 풀 수 있는 몇 가지 재밌는(?) 문제가 있어 정리해 보았습니다. Prüfer Sequence Prüfer sequence는 $n$개의 정점을 가진 labeled tree를 다음의 알고리즘에 따라 길이 $n-2$의 수열로 나타낸 것입니다. 트리를 수열로 encode한다는 의미에서 encoding 알고리즘이라고 합니다. function Tree_to_Prüfer(T=(V,E)) a <- an empty array while |V| > 2: u <- leaf node with...
-
Problem Solving과 생성함수
간혹 조합론 문제를 해결하다가 점화식이 안 나와서 좌절하고 있을 때, 이 문제는 생성함수를 이용하면 기계적으로 만들어낼 수 있다는 충격적인 코멘트를 받아 언젠가 공부해야지 마음먹고 있습니다. 아쉽게도 정규 교육과정에 포함되어있지 않아서인지 problem solving와 관련된 자료가 드물었습니다. 때문에 이 포스트를 작성하시로 하였습니다. 이 포스트는 생성함수는 무엇이고, problem solving에 적용할 수 있는 방법을 다룹니다. 생성함수란? 일반적으로, 어떤 수열 ${a_i} = (a_0, a_1, a_2, \cdots)$에 대하여, \[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots...