-
IMO 조합 문제를 DP로 풀어보자
저번 글에 이어 이번에도 IMO(국제 수학 올림피아드)와 관련된 주제를 가져왔습니다. 오늘은 아마도 이 글을 읽는 분들이 가장 익숙하실 조합 문제들을 다뤄보려고 합니다. 최근 들어 PS에서 다루는 다양한 알고리즘적 사고를 요구하는 문제들이 수학 올림피아드에도 출제되고 있습니다. 특히 DP(점화식)를 이용하는 문제가 최근 2년 연속 IMO에 출제되며 큰 관심을 끌었습니다. 이번 글에서는 이 두 문제의 풀이를 간단히 소개해보려 합니다. IMO 2022 P6 양의 정수 $n$이 있다. 노르딕 사각형이란 $n\times n$ 모양의 판으로 각 칸에 $1$부터 $n^2$까지의 수가 하나씩...
-
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개씩 선정했습니다....
-
기하 문제를 스스로 해결하는 AI
2024년 1월 17일, Solving olympiad geometry without human demonstrations이라는 논문이 Nature에 실렸습니다. 논문에 따르면, AlphaGeomtery라는 AI가 IMO(국제 수학 올림피아드)에 출제된 기하 문제 30개 중 무려 25개를 스스로 해결하였으며, 이는 IMO 금메달리스트의 성적 평균에 준하는 수준이라 합니다. 해당 글에서는 논문의 내용을 간단히 정리한 후, AI의 실제 풀이를 구체적으로 살펴보며 AI의 성능을 분석해보려 합니다. Background AI 연구에서 관심받던 주제 중 하나로, 스스로 증명을 구축하는 AI의 개발은 이전부터 다양한 연구가 진행되어 왔습니다. 해당 연구의 가장 큰 장벽은, 사람의...
-
Number Theory Techniques
https://www.acmicpc.net/category/detail/4072 해당 링크는 12월 3일에서 12월 10일까지 열렸던 BOJ Bundle이라는 백준 커뮤니티 대회이다. 이번 글에서는 대회에 사용되었던 정수론 테크닉들을 몇 개 소개해보려 한다. F. Queens’ Rye Cafe 요약: 분모가 $N$이하인 $[0, 1]$의 기약분수들을 정렬하였을 때, $a/b$의 $j$번째 다음 항을 구해야 한다. Farey Sequence의 성질을 이용하는 문제이다. 특히 이번 ICPC 2023 예선 G에 출제되면서 더욱 유명해진 것 같다. Farey Sequence란 정렬된 기약분수의 수열을 생성하는 방법이다. 기본적으로 두 기약분수 $(0/1, 1/1)$에서 시작한다. 매 차례마다 두 기약분수 $a/b$와...
-
Taylor Shift, Sampling Points Shift
개요 최근에 Polynomial Shift를 사용하는 문제를 여러 대회에서 보았기 때문에 이 글을 작성하게 되었습니다. 다항식 $f(x)$와 정수 $c$가 주어졌을 때 새로운 다항식 $f(x+c)$를 구하는 것을 Taylor Shift라고 부릅니다. $N$차 미만의 다항식 $f(x)$가 숨겨져 있고 값 $f(0), f(1), \cdots, f(N-1)$과 정수 $c,M$이 주어졌을 때 $f(c), f(c+1), \cdots, f(c+M-1)$을 구하는 것을 Sampling Points Shift라고 부릅니다. 위의 두 문제는 조합론 문제를 해결할 때 종종 유용한 도구가 되어 줍니다. 두 문제 모두 단순하게 풀면 너무 느리지만, FFT를 사용한다면 효율적으로...
-
Erdös-Ginzburg-Ziv 정리의 O(n log n) 시간 해법 찾기
Erdös-Ginzburg-Ziv 정리는 임의의 길이 $2n-1$의 정수열에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. 이전에 작성된 글에서는 $O(n^2/w)$ 풀이를 소개했지만, 최근에 공개된 이 부분수열을 직접 찾는 $\mathcal{O}(n \log n)$ 풀이에 대해서 소개합니다. Erdös-Ginzburg-Ziv 정리와 증명 Erdös-Ginzburg-Ziv 정리는 길이가 $2n-1$인 임의의 정수열 $A = { {a}_1, {a}_2, \cdots, {a}_{2n-1}}$에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. $A$에 따른 $A$의 부분수열을 Erdös-Ginzburg-Ziv 정리의 해법이라고 부릅니다. Erdös-Ginzburg-Ziv가 간단한 증명을 제시했고, 이...
-
람다 표현과 처치 인코딩(2)
이전 글에 이어서, 자연수와 그 연산들을 어떻게 함수로 인코딩하는지 알아보도록 하겠습니다. 자연수 인코딩(Church Numerals) 처치 인코딩에서는 다음과 같이 자연수를 정의합니다. \[0 = \lambda f. \lambda x. x\] \[1 = \lambda f. \lambda x. f \, x\] \[2 = \lambda f. \lambda x. f \, (f \, x)\] \[3 = \lambda f. \lambda x. f \, (f \, (f \, x))\] \[\vdots\] \[n = \lambda f. \lambda x. f^{n} \, x\] 간단히 말하자면, 처치 인코딩에서 자연수...
-
람다 표현과 처치 인코딩(1)
람다 표현(Lambda Expression)이란? 간단히 설명하자면, 람다 표현은 어떤 함수를 이름 없이 표현하는 방식이라 할 수 있습니다. 이런 특징으로 인해, 람다 표현은 종종 익명 함수(anonymous function)라고 불리기도 합니다. ‘이름 없이 표현한다’는 의미를 좀 더 와닿게 하기 위해, 한 가지 예시를 들어보도록 하겠습니다. 만약 $x$를 받아서 $x+1$을 내놓는 함수를 표현하고 싶다면 어떻게 해야 할까요? 보통의 경우, 아래와 같이 수학적인 표현법을 사용할 수 있습니다. $ f(x) = x + 1 $ 눈치채셨을지도 모르지만, 어느새 이 함수에는 $f$라는 이름이...
-
CORDIC(Volder's Algorithm)
자주 있는 일은 아니지만, 살면서 적어도 한 번쯤은 삼각함수를 사용하는 코드를 작성해야 할 일이 있을 것입니다. C++의 math.h 헤더나 Python의 math 모듈같이, 대부분의 언어에서 삼각함수를 비롯한 여러 기능을 지원하는 수학 라이브러리가 기본으로 제공됩니다. >>> from math import * >>> sin(1) # usage of sin function in Python 0.8414709848078965 그런데, 주어진 각도가 $ \pi/6 $, $\pi/4$, $\pi/3$과 같이 딱 떨어지는 특수각이 아닐 때에도 컴퓨터는 어떻게 삼각함수의 값을 구할 수 있는 걸까요? 위 예시에서 $\sin 1$의 값은...
-
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)$를 직접 구하는 간단한 공식은 알려져 있지 않고, 보통 점화식을 통해 계산합니다. 위...
-
Segment의 개수를 이용하는 순열 경우의 수 문제
소개 특정 조건을 만족하는 순열의 개수를 세는 문제 중에서, segment(이하 구간)의 개수를 이용하는 특이한 꼴의 다이나믹 프로그래밍 문제를 다뤄보려고 합니다. 예시 문제를 통해 살펴봅시다. 문제1. 길이가 $N$, Increasing segment의 개수가 $K$개인 순열의 개수 Increasing segment란, $l+1 \leq i \leq r$인 모든 $i$에 대해 $A_{i-1} < A_i$를 만족하는 $[l, r]$이라고 합니다. 단, 다른 increasing segment에 포함되는 구간은 무시하는 걸로 합시다. 예를 들어, $1\space4\space5\space2\space3\space6\space8\space7$의 increasing segment는 $[1, 3], [4, 7], [8, 8]$로 총 3개입니다. 우리는 길이가 $N$이고...
-
Understanding CRC
서론 작년 중순, 한 CTF에서 CRC와 관련된 문제가 하나 나왔습니다. 문제의 요지인 즉슨, flag{x}의 CRC 값이 다시 x가 나오게 하는 x를 구하는 것이었습니다. 이 과정에서 CRC의 특성에 대해서 이해하고 있는 사람이 별로 없다는 것을 알게 되었습니다. 또한 네트워크 수업에서도 Error code를 소개하는 자리에서 CRC가 나왔지만, CRC를 구하는 방법에 대해서만 알려줄 뿐 CRC가 어떠한 특성을 가지고 있는지는 알려주지 않았습니다. 최근에도 CRC에 대한 CTF 문제가 나오고 있고, 저도 CRC에 대해서 헷갈리던 부분이 있어서 이번에 한 번 정리하게...
-
Erdös-Ginzburg-Ziv 정리
서론 0과 1이 $X$개 있을 때, 그 중 항상 같은 수가 $N$개 이상 있게 하는 최소의 $X$는 $2N-1$이다. $X=2N-2$인 경우에는, 0과 1이 $N-1$개 존재하면 불가능하다. $X = 2N-1$개 있을 때는, 비둘기집의 원리에 의해서 항상 0이 $N$개 혹은 1이 $N$개 존재한다. 우리는 이 비둘기집의 원리의 일반화된 버전을 생각해 본다. 임의의 정수가 $X$개 있을 때, 그 중 합이 $N$의 배수가 되는 $N$개를 고를 수 있는 최소의 $X$는 얼마인가? 수로 0과 1만 가능한 것이 아니라, 모든 정수가 가능하다....
-
Rabin fingerprint for problem solving
Rabin fingerprint란? Rabin fingerprint는 길이 $n$의 배열 $m$, 임의의 값 $\space x$에 대해 아래와 같은 수식을 가지는 일종의 해시 함수입니다. $f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}$ 주로, 라빈카프 알고리즘에서 사용되기 때문에 해당 알고리즘을 공부하신 분께는 친숙할텐데요. 위 해시함수를 응용하여 문제를 해결하는 방법에 대해서 소개하고자 합니다. 모든 설명에서 $x$가 $max(m_i)$보다 큰 상황을 가정합니다. 가장 긴 문자열(링크) $m_0$ ~ $m_i$를 $g(x,\space 0,\space i) = m_0 + m_1x + … + m_{i}x^{i}$와 같이 $m_j$ ~ $m_{j+i}$를 $g(x,\space j,\space j+i) = (m_jx^{j} +...
-
Exchange argument
Exchange argument란? 임의의 상태에서 매순간 손해보지 않으면서, 원소끼리의 교환을 통해 얻어지는 상태로 나아가는 것을 반복하면 최적의 상태를 얻을 수 있다는 탐욕적인 주장입니다. 이해를 위해 다양한 문제에서의 활용을 소개해보겠습니다. 구두 수선공(링크) 우리는 주어지는 작업의 순서를 정해서 최적의 작업순서를 정해야 합니다. 임의의 작업 순서가 정해졌을 때 비용은 $ (T_{k_1}) \times S_{k_2} + (T_{k_1}+T_{k_2}) \times S_{k_3} + … (T_{k_1}+T_{k_2}+…T_{k_{n_-1}}) \times S_{k_n} $ 이 됩니다. 여기서 $ i $ 번째와 $ i+1 $ 번째의 작업의 순서를 서로 바꾸는 시행에...
-
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...
-
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...