Algorithm/D. Math & Number Theory (25) 썸네일형 리스트형 50. Pigeonhole Principle 비둘기집의 원리(Pigeonhole Principle)는 $(n+1)$개의 물건을 $n$개의 상자에 빠짐없이 넣은 경우 최소한 한 개의 상자에는 두 개 이상의 물건이 들어간다는 원리로, 보통 비둘기와 비둘기집에 빗대어 표현하기 때문에 이런 이름을 가지게 되었다. 이를 일반화하면 $n$개의 물건을 $m$개의 상자에 빠짐없이 넣었을 때 $\lceil n/m \rceil$개 이상의 물건이 들어간 상자가 하나 이상 존재한다는 의미가 된다. 이 원리를 이용해서 풀 수 있는 문제들의 경우 제대로 접근하지 못하면 괜히 어려운 풀이를 생각하다가 헤매기 쉬우므로 주의해야 한다. [연습문제] BOJ 21099. Four XOR (Platinum V) 더보기 $n$개의 수의 범위가 $10$만 이하이므로 여기서 임의로 $2$.. 49. Sieve of Eratosthenes 에라토스테네스의 체(Sieve of Eratosthenes)는 구간 내의 소수를 빠르게 찾아야 할 때 사용되는 방법이다. 이것을 이용하면 여러 개의 수를 동시에 소인수분해하는 것도 가능하고, 더 응용하면 약수의 개수나 약수의 합 등을 빠르게 구하는 것도 가능하다. 에라토스테네스의 체를 이용하여 소수를 찾는 과정은 다음과 같다. 일단 소수를 구하려는 범위 내의 수를 차례로 나열한다. 여기서는 $n=120$이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59.. 48. Prime Factorization 소인수분해(Prime Factorization)는 양의 정수를 소수들의 곱으로 나타내는 것으로 다양한 문제에서 등장하는 개념이다. 소인수분해를 하는 방법은 다양하고 응용 범위도 넓은 편이기 때문에 각각의 상황에 맞는 소인수분해 방법을 선택하는 것이 좋다. 가장 간단한 소인수분해 방법은 다음과 같다. vectorv; void f(int n) { for(int i = 2; i 47. Probability 확률론(Probability Theory)은 PS에서 자주 나오는 분야는 아니지만 관련 문제를 풀기 위해서는 기본적인 지식이 약간은 필요하다. 먼저 확률 관련 용어들의 정의는 다음과 같다. 실험(Experiment)은 관측 또는 그 절차를 의미하며, 실험의 결과로 나올 수 있는 가장 기본적인 결과를 근원사건(근원사상, Elementary Event)이라고 한다. 어떤 특성을 갖는 근원사건의 모임을 사건(사상, Event)이라고 한다. 어떤 조건 아래에서 특정한 사건 $A$가 일어날 가능성의 정도를 사건 $A$가 발생할 확률(Probability)이라고 하고, $\color{#0000FF}{P(A)}$로 나타낸다. 사건 $A$가 발생하지 않는 사건을 사건 $A$의 여사건(Complementary Event.. 46. Combinatorics 조합론(Combinatorics)은 순열과 조합, 경우의 수 등을 다루는 분야이다. 조합론 문제를 풀기 위해서는 약간의 배경지식이 필요하다. 팩토리얼(계승, Factorial)은 $0$ 이상의 정수에 대해 정의되는 함수로 $0! = 1, \color{#0000FF}{n!} = (n-1)! \times n$이다. 팩토리얼을 실수 범위로 확장한 감마 함수(Gamma Function)라는 것도 존재하지만 웬만한 알고리즘 문제를 풀기 위해서는 팩토리얼만 알고 있어도 괜찮다. 순열(Permutation): 서로 다른 $n$개의 원소 중 $r$개를 중복 없이 골라서 순서대로 나열하는 경우의 수를 $\color{#0000FF}{_n\mathrm{P}_r}$ 또는 $\color{#0000FF}{\mathrm{P}(n,.. 45. Modular Operation 모듈러 산술(Modular Arithmetic)은 정수를 특정한 모듈러 $m$으로 나눈 나머지로 정의하는 방법이다. ($m$은 $2$ 이상의 정수) 이 구조에서 실행되는 연산들을 모듈러 연산(Modular Operation)이라고 한다. 수학에서 $a$를 $b$로 나눈 나머지는 보통 $\color{#0000FF}{a \,\bmod\, b}$로 표기하고, $a$와 $b$를 $m$으로 나눈 나머지가 같을 경우 $\color{#0000FF}{a \equiv b \pmod{m}}$이라고 표기하며 이를 합동식(Congruence)이라고 한다. 대부분의 프로그래밍 언어에는 정수 나눗셈의 나머지를 구하는 $\text{%}$ 연산자가 존재하여 $a \,\bmod\, b$ 대신 $a\text{%}b$를 사용하게 된다. .. 44. Euclidean Algorithm 유클리드 호제법(유클리드 알고리즘, Euclidean Algorithm)은 두 다항식의 최대공약다항식을 빠르게 구하는 알고리즘이다. 일반적으로 차수가 $1$ 이상인 두 다항식의 최대공약다항식을 구하는 상황은 자주 발생하지 않으며 대부분 차수가 $0$인 두 다항식, 즉 두 정수의 최대공약수를 구하기 위해 유클리드 호제법을 이용하게 된다. 유클리드 호제법의 내용은 다음과 같다. ${\color{#0000FF}{\gcd(a, b)}}$는 $a$와 $b$의 최대공약다항식을 의미한다. $a$, $b$가 다항식이고 $a$를 $b$로 나눈 나머지를 $c$라고 하면 $\gcd(a,b)=\gcd(c,b)$이다. $(b \ne 0)$ 유클리드 호제법의 증명은 다음과 같다. 더보기 $a$, $b$가 $a \ge b \ge .. 43. Power by Divide and Conquer 정수론 문제를 풀기 위해서 알아 두어야 하는 두 가지 기본적인 지식이 존재하는데, 분할 정복을 이용한 거듭제곱과 유클리드 호제법이 그것이다. 분할 정복을 이용한 거듭제곱(Power by Divide and Conquer)의 기본적인 원리는 이 글에서 설명한 적이 있다. 거듭제곱 $x^y$를 구하는 두 가지 방법을 요약하면 다음과 같다. $y$를 $2$의 거듭제곱의 합으로 나타낸 다음 $x$를 제곱해 나가면서 곱을 구한다. $y$가 홀수인 경우 $x^{y-1}$과 $x$를 곱해서 답을 구하고, $y$가 짝수인 경우 $x^{y/2}$를 제곱해서 답을 구한다. 두 가지 방법의 구현은 다음과 같다. 일반적인 경우 답이 커지는 것을 피하기 위해 어떤 수 $p$로 나눈 나머지를 대신 구하게 되는 경우가 많기 때문에.. 이전 1 2 3 4 다음
