[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 전반적 내용
: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x12강 - 수학'
- 소수
- 최대공약수
- 연립합동방정식
- 이항계수
- Q&A
- 마치며
1. 소수
- 소수
: 1과 자기 자신으로만 나누어지는 수
: 약수가 2개인 수- 합성수
: 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수
1) 소수 판정법
(1) 가장 기본적인 방법. O(N)
정의 그대로 1과 자기 자신으로만 나누어지는지,
2부터 N-1까지의 수 중에서 그 수를 나누는 다른 수가 없는지 확인!
다음 코드는, n을 i로 나누어보는 연산이 최대 n-2번이므로,
시간복잡도는 O(N).
bool isprime(int n){
if(n == 1) return false;
for(int i = 2; i < n; i++)
if(n % i == 0) return false;
return true;
}(2) 발전된 방법. O(√N)
합성수 N에서 1을 제외한 가장 작은 약수는 √N이하이다.
예를 들어, N = 18일 때,
가장 작은 약수는 1을 제외한 '2'이다.
√18 = 4.xxxx이고, 2는 √18이하이다.
Pf)
합성수 N에서 1을 제외한 가장 작은 약수를 x라고 하면,
N / x 또한 1이 아닌 N의 약수가 될 것이다.
따라서 x <= (N / x)이다.
위의 식을 정리하면 x^2 <= N이므로, x <= √N이다.
따라서, 1번 방법에서는 2부터 N까지 나누었다면,
2번에서는 2부터 √N까지만 나눈다.
그렇다면 √N은 어떻게 구현을 하나.
sqrt함수는 실수의 연산/저장 과정에서 반드시 오차가 발생하므로 사용하면 안된다.
따라서 for문의 조건을, i * i <= n으로 하면 된다.
bool isprime(int n){
if(n == 1) return false;
for(int i = 2; i * i <= n; i++)
if(n % i == 0) return false;
return true;
}2) 범위 내의 소수 판정법
(1) 가장 기본적인 방법
2부터 N까지 소수 판별법을 적용.
소수 판별법은 O(√N), 이걸 N개에 대해 적용하므로
시간 복잡도는 O(N√N).
(2) 조금 발전된 방법
1번 방법에서 소수 판별법을 진행할 때,
2 ~ √N 사이의 모든 수를 나눔.
이 때, 모든 수가 아닌, 2 ~ √N 사이의 소수로만 나눔!!
(3) 에라토스테네스의 체. O(NlglgN)
2부터 시작해, 각 소수의 배수들을 지워나가 N까지 탐색하는 방식.
(= 합성수를 제외하는 방식)
예를 들어, 2가 소수로 판별되면 2의 배수인 4, 6, 8, ...을 모두 false로 만듦.
다음으로 3이 소수로 판별되면 3의 배수인 6, 9, 12, ...을 모두 false로 만듦.
이 때, 이미 false로 판별된 수는 소수가 아니므로 제외하고 다음 수를 탐색한다.
이 때, 조금 더 발전시키면,
2를 통해, 4, 6, 8, 10, ...
3을 통해, 6, 9, 12, 15, ...
4를 통해, 8, 12, 16, 20, ...이 소수로 판별되었음.
5에서 탐색할 때, 10, 15, 20, 25, ...에서 25의 앞 10, 15, 20은 이미 앞의 과정을 통해 소수로 판별되었음.
이는 이 수들이 5보다 작은 소인수를 가지고 있음을 의미함.
따라서, 5에서 탐색할 때, 5^2 = 25부터 false로 바꿔가면 됨.
(이는 5뿐만 아니라, 모든 수에서 적용가능함. 2, 3, 4, ...)
vector<int> sieve(int n){
vector<int> primes;
vector<bool> state(n + 1, true);
state[1] = fasle;
for(int i = 2; i * i <= n; i++){
if(!state[i]) continue;
for(int j = i * i; ij <= n; j += i)
state[j] = false;
}
for(int i = 2; i <= n; i++)
if(state[i]) primes.push_back(i);
return primes;
}참고로 state변수를 vector<bool 자료형임.
왜 bool배열로 하지 않은 이유는, 배열로 잡으면 시간이 꽤 느려짐.
bool은 1byte를 차지하는데, 만약 vector<bool>로 두면 한 칸이 1byte가 아닌 1bit만 차지하도록 최적화됨.
덕분에 공간도 8배 적게 쓰고, cache hit rate가 올라가서 시간도 빨라짐.
이런 식의 최적화를 거치게 되면 시간복잡도는 O(NlglgN)인데, 거의 O(N)과 비슷함.
3) 소인수분해(Factorization)
- 소인수분해(Factorization)
: 정수를 소수의 곱으로 나타내는 것
(1) 에라토스테네스의 채를 이용
에라토스테네스의 채를 이용해,
N이하의 모든 소수를 N으로 나누어보는 방법
(2) 발전된 방법
N을 나누는 수를, 2부터 시작해 1씩 증가시켜, 나누어질 수 없을 때까지 나누는 방법.
(2.1) 방법의 정당성
이 방법이 소인수 목록을 잘 구하는가?
-
소인수 목록에 적힌 수들을 모두 곱했을 때 N이 되는가?
-
목록에 있는 수들이 전부 소수인가?
우선 1번은 당연한 것.
이 방법은 N에서 각각의 수를 나누었기 때문.
2번은 만족하는가?
나누는 수를 2에서부터 1씩 증가시키지만, 따로 소수인지 판별하지 않았음.
하지만 결론적으로 말하면 반드시 다 소수임!!
만약 소인수목록에 소수가 아닌 수가 있다고 가정을 해보자.
그 수는 소수가 아닌 반드시 합성수가 될 것.
합성수는 소수인 약수를 반드시 가짐.
만약 15라는 소인수목록이 있다면, 15는 3과 5라는 소수인 약수를 가짐.
하지만 15까지 가기 이전에 이미 3인 순간에서, N은 더 이상 3으로 나누어질 수 없을 때까지 나누어짐.
따라서 소인수목록으로 3의 배수의 15는 나올 수 없음.
위의 귀류법과 같은 논리로, 만약 소인수목록으로 합성수가 있다면, 그 합성수에는 소인수 p가 있을 것이지만, 이미 그 합성수로 가기 전에 N에는 p가 남아있지 않은 것이므로 모순임.
(2.2) 시간복잡도의 개선
일단, 시간복잡도는 N이 소수라면 중간에 나눠지는 과정 없이 i가 N까지 올라가야 하므로 O(N)의 시간복잡도를 가짐.
하지만 이를 O(√n)으로 만들 수 있음.
소수 판정 알고리즘과 비슷함.
N을 i로 나누는 이유는 소인수 i를 빼내기 위함.
그렇다면 i * i가 N보다 커지게 되면 더 이상 나누는 작업을 할 필요가 없음.
(이미 N에는 √n이하의 소인수가 없기 때문
= N은 소인수임)
예를 들어, 1100을 소인수분해 한다고 했을 때,
| N | i | 소인수목록 |
|---|---|---|
| 1100 | 2 | |
| 550 | 2 | 2 |
| 275 | 2 | 2, 2 |
| 275 | 3 | (변화 X) 2, 2 |
| 275 | 4 | (변화 X) 2, 2 |
| 275 | 5 | 2, 2 |
| 55 | 5 | 2, 2, 5 |
| 11 | 5 | 2, 2, 5, 5 |
| 11 | 6 ~ 10 | (변화 X) 2, 2, 5, 5 |
| 1 | 11 | 2, 2, 5, 5, 11 |
위와 같은 과정을 거친다.
이 때, 밑에서 3번째 과정을 보게 되면,
i가 5이고, N은 11이다.
i * i = 25 > N = 11을 만족하므로,
N은 √N이하의 소인수가 없으므로(N은 소인수이므로),
소인수목록에 N(=11)을 뒤에 추가하면 된다.
(3번째 과정의 뒤의 과정은 필요가 없게 된다.)
정리하면,
소수판정과 소수판별은 모두 O(√n)임.
그리고 1부터 N까지 수 중에서 소수 목록을 구하는 것은 에라토스테네스의 체를 쓰면 됨.
2. 최대공약수(Greatest Common Divisor, GCD)
1) 약수
- 약수
: 어떤 수를 나누어떨어지게 하는 수
: 1부터 N까지 for문을 돌면서 다 나눠보면 구할 수 있음. O(N).
하지만 이 역시 마찬가지로 O(√n)에 가능.
18의 약수는 1, 2, 3, 6, 9, 18.
1 * 18, 2 * 9, 3 * 6로 표현 가능한데,
1, 2, 3만 구하면 나머지 약수는 자동으로 구해짐.
곱해서 N이 되는 두 수를 생각하면, 작은 수는 √n이하이므로, √n까지만 반복하면 됨.
(단 N이 제곱수일 때, 예를 들어 N이 16일 때는 √16 = 4는 약수에 1번만 포함시켜야 함.)
vector<int> divisor(int n){
vector<int> div;
for(int i = 1; i * i <= n; i++)
if(n % i == 0) div.push_back(i);
for(int j = (int)div.size() - 1; j >= 0; j--){
if(div[j] * div[j] == n) continue;
div.push_back(n / div[j]);
}
return div;
}두번째 for문에서 int로 형변환을 시켜줘야한다.
왜냐하면 size()함수는 unsigned를 반환하는데, 만약 size가 0이라면 0 - 1로 -1이 아닌 (unsigned int의 최댓값 - 1)을 값으로 가짐.
(하지만, 이 상황에서 1은 반드시 포함되므로 size - 1을 해도 최소 0이 되므로, overflow가 발생하지만, 이를 int j에 넣을 때 다시 형변환이 일어나 j에 -1이 정상적으로 담김. 하지만 이상적이지는 않은 과정임.)
2) 최대공약수(Greatest Common Divisor, GCD)
- 약수
: 두 자연수의 공통된 약수 중 가장 큰 약수
1) 기본적인 방법
두 수의 약수 목록을 다 찾아서, 정렬을 하거나 또는 초기 상태에서 겹치는 약수를 찾고, 그 중 최댓값을 찾으면 됨.
2) 유클리드 호제법
- 유클리드 호제법
: 두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 하면, GCD(A, B) = GCD(B, r)이다.
예를 들어, A를 20, B를 12로 하면,
A를 B로 나눈 나머지는 8(= 20 % 12).
GCD(20, 12) = GCD(12, 8) = GCD(8, 4) = GCD(4, 0)이다. 이 때, 0은 모든 수이 배수이므로, 최대공약수는 4가 된다.
int gcd(int a, int b){
if(a == 0) return b;
return gcd(b % a, a);
}위에서는 재귀를 사용했지만, whlie을 이용해서 구현할 수도 있고, 시간복잡도도 O(log(max(a,b)))라서 굉장히 빠름.
그리고 C++17에서는 gcd함수가 numeric헤더 파일 안에 내장되어 있음.
3) 최소공배수(Least Common Multiple, LCM)
- 최소공배수
: A B = GCD(A, B) LCM(A, B)
int lcm(int a, int b){
return a / gcd(a, b) * b;
}위에서 overflow 방지를 위해 a를 먼저 gcd로 나누어줌.
3. 연립합동방정식
-
4. 이항계수
1) 기본적인 방법
int n, k; cin >> n >> k;
int ret = 1;
for(int i = 1; i <= n; i++) ret *= i;
for(int i = 1; i <= k; i++) ret /= i;
for(int i = 1; i <= n-k; i++) ret /= i;
cout << ret;2) 발전된 방법
nCk = n-1Ck + n-1Ck-1
만약 5개 중에서 3개를 뽑는다고 하면 5C3.
- 내가 찜한 상자 1개 + 나머지 4개 중에서 2개 픽
- 내가 찜한 상자 0개 + 나머지 4개 중에서 3개 픽
이는 dp로 해결 가능.
d[i][j] = iCj라 하면, d[i][j] = d[i-1][j-1] + d[i-1][j]로 표현 가능.
#include <bits/stdc++.h>
using namespace std;
int comb[1002][1002];
int mod = 10007;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 1; i <= 1000; i++){
comb[i][0] = comb[i][i] = 1;
for(int j = 1; j < i; j++)
comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
}
int n, m; cin >> n >> m;
cout << comb[n][m];
}5. Q&A
-
6. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 전반적 내용
: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x12강 - 수학'
