본문 바로가기

Algorithm

 (143)
48. Prime Factorization 소인수분해(Prime Factorization)는 양의 정수를 소수들의 곱으로 나타내는 것으로 다양한 문제에서 등장하는 개념이다. 소인수분해를 하는 방법은 다양하고 응용 범위도 넓은 편이기 때문에 각각의 상황에 맞는 소인수분해 방법을 선택하는 것이 좋다. 가장 간단한 소인수분해 방법은 다음과 같다.vectorv;void f(int n){ for(int i = 2; i $2$ 이상 $n$ 이하의 모든 정수를 확인하면서 $n$이 $i$의 배수이면 $i$를 소인수 목록에 추가하고 $n$을 $i$로 나눈 다음 계속 진행한다. 하지만 이 방법은 $n$이 $1$억 정도의 소수일 경우 성능이 상당히 떨어진다. 다행히도 위의 코드를 조금만 수정하면 성능은 매우 좋아진다.vectorv;void f(int n){ ..
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 0$..
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$로 나눈 나머지를 대신 구하게 되는 경우가 많기 때문에 코드..
42. Math & Number Theory Intro 카테고리 D에서는 수학, 정수론, 게임 이론에 관한 내용을 다룬다. 다루는 주제는 다음과 같다. 기초 정수론 조합과 확률 소수와 모듈러 연산 소인수분해 기초 정수론의 확장 유용한 정리와 원리 선형대수학/행렬 게임 이론 빠른 곱셈 이산 구조에서의 로그와 제곱근 선형 점화식의 빠른 계산 정수론이라는 주제는 다양한 수식과 증명들을 포함하기 때문에 상당히 난해할 수 있는 부분들이 있지만 알아 두면 다양한 문제를 해결하는 데 여러모로 도움이 된다. 다음 글에서부터 위에 제시된 $11$가지 주제를 자세히 살펴볼 것이다. → solved.ac tag: math → solved.ac tag: number_theory
40. Parametric Search 매개변수 탐색(Parametric Search)은 최적화 문제를 결정 문제로 변형한 뒤 이분 탐색, 삼분 탐색 등을 이용하여 답을 찾아내는 탐색 방법이다. 예를 들어 어떤 함수 $f(x)$가 특정 구간에서 증가하고 $f(x)$가 $k$ 이상이 되는 최소의 $x$를 찾아야 할 경우 해결해야 하는 것은 주어진 조건을 만족하는 $x$의 최소값이므로 이것은 최적화 문제이다. 하지만 단순히 $f(x)$가 $k$ 이상인지를 판별하는 것은 참, 거짓만 확인하면 되므로 결정 문제가 된다. 또한 이 결정 문제의 답은 $x$가 특정 값보다 작다면 거짓, 그렇지 않다면 참이므로 참, 거짓의 기준이 되는 $x$를 이분 탐색으로 찾아낼 수 있다. 이 방법을 응용하면 일부 조건이 '최대의 $x$', '$k$ 초과', '$k$ 미..

티스토리툴바