[알고리즘기초] 수학1
나머지 연산
컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다.
- (A+B) mod M = ( (A mod M) + (B mod M) ) mod M *
- (A\_B) mod M = ( (A mod M) \ (B mod M) ) mod M **
나누기의 경우는 성립하지 않음
뺄심의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야함
- (A-B) mod M = ( (A mod M) - (B mod M) ) mod M *
뺄샘의 경우 부호는 언어마다 다름 ..
-2 % 3 = -2 ? 인지 1 ? 인지 ..
python의 경우 1
C, C++, JAVA의 경우 2
- 0 <= (a%c) < c
- 0 <= (b%c) < c
이므로 (a%c - b%c) 는
-c < (a%c - b%c) < c 를 만족한다.
따라서, (a%c - b%c + c) 는 0보다 큰 값을 갖기 때문에, 이 상태에서 다시 c로 나눠주면 원하는 결과를 얻을 수 있다.EX : -2 % 3 = (-2 + 3) % 3 = 1
최대공약수
Greatest Common Divisor (GCD)
- 두수 A,B 의 최대공약수 G는 A,B의 공약수 중에서 가장 큰 정수
- 최대공약수가 1 인 두수를 서로소(Coprime)라고 한다.
int g = 1;
for (int i = 2; i <= min(a,b); i++) {
if (a % i == 0 && b % i == 0) {
g = i;
}
}
: 시간복잡도 -> a,b의 최댓값을 N = max(a,b) 라고 한다면 O(N)
--> 더 좋은 방법 : 유클리드 호제법
a를 b로 나눈 나머지를 r 이라고 했을 때
GCD(a,b) = GCD(b,r) 과 같다.
r 이 0이면 그때 b가 최대공약수이다.
GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8
- 재귀 함수를 사용해서 구현한 유클리드 호제법
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a%b);
}
}- 재귀함수를 사용하지 않고 구현한 유클리드 호제법
int gcd(int a, int b) {
while (b != 0) {
int r = a%b;
a = b;
b = r;
}
return a;
}위 알고리즘의 시간 복잡도는 O(logN)
최소공배수
Least Common Multiple (LCM)
두 수의 LCM은 두 수의 공배수 중 가장 작은 정수
최대공약수를 통해서 구할수 있다.
a * b = GCD(a,b) * LCM(a,b) 와 같기 때문에
두수 a,b의 GCD를 g 라고 했을 때
LCM(a,b) = g * (a/g) * (b/g)
소수 (Prime Number)
약수가 1과 자기자신 밖에 없는 수
2보다 크거나 같고, N-1보다 작거나 같은 ( = 자기자신보다 작은) 자연수로 나누어 떨어지면 안된다.
소수와 관련된 알고리즘은 2가지가 있다.
1. 어떤 수 N이 소수인지 아닌지 판별하는 방법
bool prime (int n) {
if (n < 2) {
return false;
}
for (int i=2; i <=n-1; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}시간복잡도 O(N)
-- 더 나은 방법
N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
why ? N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문
N = a * b 로 나타낼 수 있는데, a가 작을수록 b는 크다.
가능한 a 중에 가장 작은 값은 2 이기 때문에, b는 N/2를 넘지 않는다.
bool prime (int n) {
if (n < 2) {
return false;
}
for (int i=2; i <=n/2; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}O(N/2) = O(N)
-- 진짜 빠른 방법
N 이 소수가 되려면, 2보다 크거나 같고, 루트N 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
why ? N 이 소수가 아니라면, N = a * b 로 나타낼 수 있다. (a <= b)
(a > b 라면 두수를 바꿔서 항상 a <= b 로 만들 수 있다.)
두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.
따라서, 루트 N 까지만 검사를 해보면 된다.
N이 소수가 아니라면, a <= 루트N, b >= 루트N이다.
( a < 루트N, b < 루트N이라면 a*b < N 이 되고,
a > 루트N, b > 루트N이라면 a*b > N 이 되므로 항상 a <= 루트N, b >= 루트N이다. )
한쪽에서 약수가 없어야 함 .. 루트N까지 나누어떨어지는 약수가 없으면 소수라고 할수있다.
bool prime (int n) {
if (n < 2) {
return false;
}
for (int i=2; i*i <=n; i++) { // i <= 루트 N .. 실수인데, 실수는 분사값이므로 사용하지 않는게 좋으므로 양변 제곱 i*i <= N
if (n%i == 0) {
return false;
}
}
return true;
}시간복잡도 : O(루트N)
2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 ( N 이하의 소수)
N이하의 소수에 대해서 "2보다 크거나 같고, 루트N보다 작은 자연수로 나누어 떨어지는 약수가 없으면 소수" 인 방법 이용 -> 각각의 수마다 루트N만큼의 시간이 걸리니까 시간복잡도 O(N루트N)
-- 더 빠른 방법 (범위의 소수를 구할땐)
에라토스테네스의 체
100 이하의 소수를 구하면 다 써놓고,
지워지지 않은 수 중에서 가장 작은수는 2이다.
2는 소수이고, 2의 배수는 모두 소수가 아니다 -> 2의 배수를 모두 지운다. ( 이 과정을 계속 반복)
3은 소수이고, (3이 소수가 아니라면 이전에 지워졌어야 한다.) 3의 배수를 지운다.
(지워지지 않은 수중에 가장 작은 수 ) 5는 소수이고, 5의 배수를 지운다.
7은 소수이고, 7의 배수를 지운다.
11의 배수부턴 (11*11 = 121)로 100을 넘기 때문에 수행할 필요가 없다.
남아있는 모든 수가 소수이다.
어떤 수의 제곱보다 작은 수는 지워져 있다는게 보장이 된다.
큰 수는 지워져 있을수도 있고 아닐수도 있어서 검사를 해야한다.
int prime[100]; // 소수 저장
int pn=0; // 소수의 개수
bool check[101]; // 지워졌으면 true
int n = 100; // 100까지 소수
for (int i=2; i<=n; i++) {
if (check[i] == false) {
prime[pn++] = i;
for (int j=i*i; j<=n; j+=i) { // i*i 보단 i+i 또는 ix2 가 낫다. i = 백만일 경우 제곱 : 일조 .. 인트는 21억까지
check[j] = true;
}
}
}- 1부터 N까지 모든 소수를 구하는 것이 목표이기 때문에, 구현할 때는 바깐 for문 (i)를 N까지 돌린다.
- 안쪽 for문 (j)는 N의 크기에 따라서, i*i 또는 i*2로 바꾸는 것이 좋다.
백만인 영우 i*i는 범위를 넘어가기 때문
시간복잡도는 구하기 힘든데 찾아보면 NloglogN
에라토스테네스의 체 는 소수를 구할 때 가장 빠르고 정확한 알고리즘
골드바후의 추측
2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다. -> 아직 증명되지 않았지만, 10의18제곱 이하에서는 참인것이 증명됨.
골드바후의 약한 추측..
5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
팩토리얼 Factorial
N! = 1 * 2 * ... * N
팩토리얼은 매우 큰 값
문제 ) 팩토리얼 0의 개수
N! 의 0이 몇개인지 알아내는 문제
C++, JAVA 정수의 범위가 정해져 있어서.. 20!만 되도 int범위 넘을듯 두 언어는 ... java는 bininteger.. python은 정수길이가 무제한임에도 구할수 없음. 수가 길어지면 뺄샘 덧셈 시간복잡도가.. 1이라고 할 수 없음.
10! = 3628800 -> 0이 2개인 이유는 10!을 소인수분해 해보면 알 수 있다.
-> 0을 만들 수 있는 방법은 2 * 5 밖에 없기 때문
소인수 분해를 해서 2*5가 몇개 있는지 새워봐야 한다.
10! = 2의6 * 3의4 * 7 * (2의2 * 5의2)
2의 갯수는 항상 5의 갯수보다 많다. 그렇기때문에 5의 갯수가 몇개인지 세어봐야 한다.
5만 몇개나오는지 세어보면 된다. 계속 5로 나누어 준다.
1부터 100까지 다 써본것을 곱하면 100!
인수로 5가 들어가는것
100/5 = 20 -> 5인수가 적어도 하나 들어가는 애들
100/25 = 4 (5가 2개씩 들어가는거) -> 2개 들어가는 애들
-> 24개
문제 ) 조합 0의 개수
nCm의 0의 개수 : n! / (n-1)! m!
수학은 제일 중요한건 소수......