PS 이야기

1) 중국인의 나머지 정리 중국인의 나머지 정리는 PS를 하면서 간혹 등장한다. 답이 큰 경우 일반적으로 $M$으로 나눈 나머지를 출력하라고 한다. 하지만 이 $M$이 고정되어 있지 않고, 입력으로 $k$가지가 주어진다고 할 경우 $k$ 개 경우에 대해서 매번 다 계산하면 오래걸린다. 이럴 때 필요한 것이 바로 중국인의 나머지 정리다. 정리) 서로소인 $k$개의 자연수 $n_1, n_2, \dots, n_k$와 임의의 정수 $a_1, a_2, \dots, a_k$가 있을 때, 임의의 $i (1 \leq i \leq k)$에 대해 $x \equiv a_i (\mod n_i)$ 로 표현되는 변수 $x$의 연립 합동 방정식에 대해, 이 방정식이 성립하는 해 $x = a$가 항상 존재하며, $n_1 n_2 \d..

고속 푸리에 변환은 이산 푸리에 변환(Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘으로 알려져 있다. 이에 대한 이론적인 설명을 자세하게 하려는 목적은 아니다. FFT가 PS에 어떤 식으로 응용될 수 있는지에 대해서 아주 간단하게 소개하고자 한다. PS 문제들을 풀다보면 FFT를 사용해야하는 경우를 대면하게 되는데, 이러한 문제들은 백날 생각해도 모르면 못 풀고, 조금을 생각하더라도 알면 푼다고 생각하기 때문에 꼭 알아둬야 되는 부분이라고 생각한다. 우선, PS에서 FFT가 사용되는 대표적인 예는 convolution를 $O(n \log_2 n)$만에 계산할 때이다. Convolution이란, 여기에서 설명된 것 처럼 크기가 $n$인 배열 $a..

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다. Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다. 포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다. 1) 집합이 두 개인 경우$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다. 2) 집합이 세 개인 경우세 개의 유한 집합 $A..

님 게임(Nim game)은 수학적 전략 게임이다. 여러 개의 돌 무더기가 있다. 두 사람이 서로 차례를 번갈아가면서 게임한다. 자신의 차례에 하나의 돌 무더기를 선택하여 1개이상 원하는 만큼의 돌을 제거할 수 있다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다.님 게임에 대한 이해를 돕기 위한 플래시 게임이 있다. http://www.gamedesign.jp/flash/nim/nim.html님 게임에는 수학적 필승 전략이 있다. 중,고등학교 수준의 KOI, IOI에서는 님 게임 관련 문제가 안나온다. 그렇다고해서 이해하기 어려운건 전혀 아니다. 그 전략은 간단하며, 아래와 같다.자기 차례에 각 돌 무더기에 있는 돌의 개수를 XOR($\oplus$) 연산 했을 때 값을 0으로 만들어주면 이긴다. ..