2021. 1. 23. 19:23ㆍ알고리즘/알고리즘 정리
소수(prime number)
소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다.
소수의 반대: 합성수(composite number): 세 개 이상의 양의 약수를 갖는 자연수
가장 단순한 소수판별:
2 부터 n -1 까지 모든 수를 순회, n의 약수가 있는지 확인
(합성수의 성질에 따라 sqrt(n)이하 까지 순회하도록 최적화 가능)
(비트 수에 따라 수행시간이 증가 => 비트 수가 하나 증가 => 수행시간 두배 => 지수시간)
(1, 2, 3 제외 한 모든 소수는 6k +- 1 형태임을 이용할 수 도 있다.)
(2 를 제외하면 모든 짝수는 소수가 아니다.)
1
2
3
4
5
6
7
8
9
10
|
bool isPrime(int n)
{
if(n <= 1) return false;
if(n == 2) return true;
if(n%2 == 0) return false;
int sqrtn = int(sqrt(n));
for(int i = 3; i < sqrtn; i+=2)
if(n%i == 0) return false;
return true;
}
|
cs |
소인수 분해(prime factorization):
한 합성수를 소수들의 곱으로 표현하는 방법을 찾는것
2부터 시작해 n의 소인수가 될 수 있는 수들을 하나하나 순회.
n의 약수를 찾을 때 마다 n을 이 숫자로 나눈다.
최적화 :입력의 최대값 max에 대하여 sqrt(max)까지의 소수들을 미리 찾아두고
[2, sqrt(n)]의 범위의 모든 정수 대신 소수들로만 나눔.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
vector<int> factorSimple(int n)
{
vector<int> ret;
int sqrtn = int(sqrt(n));
for (int div = 2; div <= sqrtn; div++)
while(n%div==0)
{
n /= div;
ret.push_back(div);
}
if(n>1) ret.push_back(n);
return ret;
}
|
cs |
에라토스테네스의 체(sieve of Eratosthenes):
주어진 n이하의 소수들을 모두 찾아냄.
먼저 2의 배수들을 지움.
지워지지 않은 수 중 첫번째 수 3의 배수들을 다 지움
다음으로 5를 지움...
지우고 나온 남은 수들 첫번째의 배수를 다 지우면
작업을 다 한 뒤 남은 것들은 결국 소수가 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
bool isPrime[INT32_MAX];
int n;
void eratosthenes()
{
memset(isPrime, 1, sizeof isPrime);
isPrime[0] = isPrime[1] = false;
int sqrtn = int(sqrt(n));
for(int i = 2; i <= sqrtn; i++)
if(isPrime[i])
for(int j = i*i; j <= n; j+=i)
isPrime[j] = false;
}
|
cs |
에라스테네스의 체의 문제점은 메모리 사용량이다.
많은 수에 대해 수행해야 할 때는 짝수를 별도로 처리해서 필요한 배열의 크기를
절반으로 줄여야한다.
또는 비트마스크 기법을 이용하여 최적화한다.
에라토스테네스의 체를 이용한 소인수 분해
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
|
int minFactor[INT32_MAX];
int n;
void eratosthenes()
{
for(int i = 2; i < n; i++) minFactor[i] = i;
minFactor[0] = minFactor[1] = -1;
int sqrtn = int(sqrt(n));
for(int i = 2; i <= sqrtn; i++)
if(minFactor[i] == i)
for(int j = i*i; j <= n; j+=i)
if(minFactor[j] == j)
minFactor[j] = i;
}
vector<int> factor()
{
vector<int> ret;
while(n > 1)
{
n/=minFactor[n];
ret.push_back(minFactor[n]);
}
return ret;
}
|
cs |
유클리드 알고리즘
최대 공약수를 구하는 알고리즘.
최대 공약수를 g라고 하자
A = a*g , B = b*g
A - B = (a-b)*g
두 수의 뺀 값은 최대 공약수를 유지하며
이는 계속해서 뺄셈하면 결국 최대 공약수를 얻을 수 있음을 의미한다.
하지만 엄청 큰 수와의 최대 공약수를 구하는 문제는 위와 같이 해결하면
시간이 꽤 걸리게 된다.
이를 해결하는 방법은 나머지를 취하는 것이다.
(작은수의 배수를 한꺼번에 빼는것)
1
2
3
4
5
|
int gcd(int a, int b)
{
if(a == 0) return b;
else gcd(b%a, a);
}
|
cs |
A = gcd * x
B = gcd * y
LCM = gcd * x * y
GCD * LCM = A*B
GCD(a, b) = d <===> ax + by = d(Bezout's Identity)
모듈라 연산(modular arithmetic)
모듈라 연산이란, 모듈로 M에 도달하면 다시 0으로 돌아가는 정수들을 가지고 하는 연산이다.
모듈로 연산에서 모든 정수는 M으로 나눈 나머지로 표현된다.(24시간 시계)
큰 정수를 다뤄야 하는 문제에서 자주 쓰임
모듈라 덧셈, 뺄셈, 곱셈
a%m = a' ... a = xm + a'
b%m = b' ... b = xm + b'
(a+b) =(x + y)*m + (a' + b')
(a+b)%m = (a'+b')%m
(a-b)%m = (a' - b' + m) %m ... 음수가 될 수 있기 때문에
(a*b)%m = (a'*b')%m
****모듈라 나눗셈**** 따로 정리 필요
나눗셈에 대해서는 일반적인 공식이 성립하지 않는다.
모듈라 연산에서의 나눗셈 a/b는 b로 나누는 대신
b의 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어짐.
(f 와 어떤 수 a가 주어질 때 f(a, b) = f(b, a) = e인 b가 유일하면 b는 a의 역원)
(f(a,b)의 항등원 e 는 f(x, e) = x를 항상 보장하는 수)
곱셈 역원은 항상 존재하는게 아니라 b와 m이 서로소일 때만 존재
모듈라 연산은 정수만을 다루기 때문에 나누어 떨어지지 않으면 나눌 수 없음.
따라서 m이 소수이면 다음과 같다. (페르마의 소정리)
modInv(b,m) = b^(m-2)%m
(a/b)%m= (a*modInv(b,m))%m
m이 소수가 아닌경우 다음과 같인 식을 만족하는 A를 찾으면 된다.
(디오판틴 방정식, 확장 유클리드 알고리즘)
A*b + B*M ≡ 1 (mod M)
확장 유클리드 알고리즘(Extended Euclidean algorithm)
유클리드 알고리즘은 한 수에서 다른 수를 빼는 과정을 반복하기 때문에.
gcd(p,q)을 수행하는 도중에 출현하는 모든 수는 p, q의 가중치 합인
ap + bq로 쓸 수 있다.
ex gcd(6, 15) = gcd(9, 6) = gcd(3,6) = gcd(3,3) = gcd(0,3) = 3
gcd(9, 6) 에서 9 = -1*6 + 1*15
gcd(3,6) 에서 3 = 1*9 + -1*6 = -2*6 + 1*15
따라서
gcd(p, q) = a*p + b*q
이때 유클리드 알고리즘에 코드를 적절히 추가해 최대 공약수와 함께
a,b를 반환할 수 있다. 이와 같은 알고리즘을 확장 유클리드 알고리즘이라한다.
중국인 나머지 정리
오래된 중국 수학책에서 처음 등장했다고해서 이름이 중국인 나머지 정리이다.
n개의 사과를 세명에서 같은 개수 -> 두개남음
한명 더불러서 네명에서 같은 개수 -> 세개남음
한명 더불러서 다섯명에서 같은 개수-> 한개남음
최소 n은 얼마인가?
위와 같은 형태의 문제를 풀 수 있게하는 정리이다.(연립 합동식)
중국인 나머지 정리를 이용 -> 확장 유클리드 알고리즘을 통해 답을 구함.
뤼카의 정리
모듈라 연산을 이용한 이항 계수(n r)을 빠르게 구할 수 있게 해주는 정리.
모듈라 연산을 이용하지 않을 경우엔 계산하기 어려울 정도로 큰 n 과 r에 대해
이항 계수를 계산할 수 있도록 해줌
-알고리즘 문제해결전략 516p
'알고리즘 > 알고리즘 정리' 카테고리의 다른 글
[부분 합] Partial sum (0) | 2021.01.28 |
---|---|
[계산 기하] Computational geometry (0) | 2021.01.26 |
[수치 해석] Numerical analysis (0) | 2021.01.22 |
[결정 문제] 최적화 문제를 결정문제로 바꿔 풀기 (0) | 2021.01.21 |
[완전 탐색] Combinatorial search 조합 탐색 (0) | 2021.01.19 |