수학

1. 나머지 연산

2. 최대공약수와 최소공배수

3. 소수

4. 에라토스테네스의 체

5. 골든바흐의 추측

6. 관련문제

 

수학문제 복습!

---

1. 나머지 연산(Modular Arithmetic)

컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 

답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다.

 

예를 들어, 다이나믹 문제를 풀때 경우의 수가 너무 큰경우 int값이나 long 값을 넘어서,

값을 처리를 하기 위해서 큰 정수값(big integer)을 구현하기 보다는 몇으로 나눈 나머지를 처리하라는 문제가 많다.

 

(A+B) mod M = ((A mod M) + (B mod M)) mod M
(AXB) mod M = ((A mod M) X (B mod M)) mod M
나누기의 경우에는 성립하지 않는다.(Modular Inverse를 구해야 함)
뺄셈의 경우에는 먼저 mod연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.
(A-B) mod M = ((A mod M) - (B mod M) + M) mod M

(A+B) mod M = ((A mod M) + (B mod M)) mod M
(AXB) mod M = ((A mod M) X (B mod M)) mod M
나누기의 경우에는 성립하지 않는다.(Modular Inverse를 구해야 함)
뺄셈의 경우에는 먼저 mod연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.
(A-B) mod M = ((A mod M) - (B mod M) + M) mod M

 

2. 최대공약수(Greatest Common Divisor)와 최소공배수(Least Common Multiple)

두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.

 

최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이다.

//시간복잡도 O(N)
int GCD = 1;
for(int i = 2; i <= min(a,b); ++i) {
	if(a % i == 0 && b % i == 0) {
    	GCD = i;
    }
}

 

 유클리드 호제법(Eucildean algorithm)을 이용하면 앞 알고리즘보다 더 빠른 시간내에 구할 수 있다.

//재귀
int gcd(int a, in b) {
	if(b == 0) {
    	return 0;
    } 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;
}

GCD(a,b) = GCD(b, a%b) 임을 이용하여 빠른 시간내에 풀 수 있다.(a와b의 대소관계는 구별할 필요 없다.)

세 수의 최대공약수는 다음과 같이 구할 수 있다.

GCD(a, b, c) = GCD(GCD(a, b), c)

네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다.

 

두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.

최소공배수는 GCD를 응용해서 구할 수 있다. 

두 수 a, b의 최대공약수를 g라고 했을 때

최소공배수 = g*(a/g)*b(/g)

최소공배수 문제를 풀때는 범위를 항상 체크해서 올바른 자료형이 올 수 있도록 하는 것이 중요하다.

 

 

3. 소수(Prime Number)

소수 : 약수가 1과 자기 자신 밖에 없는 수

소수를 구하는 가장 쉬운 알고리즘은 2부터 N-1까지 나눠보고 나눠지면 false를 리턴하는 것이다

고로 시간복잡도는 O(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;
}

하지만 N-1까지 검사할 필요는 없다.

루트N까지만 검사하면 소수인지 아닌지 알 수 있다.

//시간복잡도 : O(√N)
bool prime(int n) {
	if(n < 2) {
    	return false;
    }
    for(int i = 2; i*i <= n; ++i) { //루트N을 사용하지 않고 정수로 표현
    	if(n % i == 0) {
        	return false;
        }
    }
    return ture;
}

루트N을 표현 할 경우, 컴퓨터에서 실수는 근사값을 나타내기 때문에, 오차가 있다.

고로 정수로 표현하는 것이 좋다.

 

어떤 수 N이 소수인지 아닌지 판별하는데 걸리는 시간은 O(√N)이다.

그럼 1부터 1,000,000까지 모든 소수를 구하는데 걸리는 시간복잡도는 몇일까?

단순하게 풀이하면 생각한다면, 각각의 수에 대해서 소수인지 아닌지 검사해야 하고

각각의 수에 대해서 O(√N)의 시간이 걸린다.

수는 총 N개이기 때문에, O(N√N)이 걸린다.

1,000,000 * 1,000 = 1,000,000,000 = 10억 = 10초

 

이것 보다 더 빠른 방법이 존재하다.

 

4.에라토스테네스의 체(Sieve of Eratosthenes)

* 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

1. 2부터 N까지 모든 수를 써놓는다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수는 소수이다.

4. 이제 그 수의 배수를 모두 지운다.

만약 1부터 100까지 소수를 구한다면, 2, 3, 5, 7을 순서대로 지우면 된다.

(11의 제곱은 121로 100을 넘기 때문에 11의 배수는 지울 필요 없다.)

5. 남아있는 모든 수가 소수이다.

int p[100];		//소수저장
int pn = 0;		//소수의 개수
bool c[101];	//지워졌으면 true
int n = 100;	//100까지 소수
for(int i = 2; i <= n; ++i) {
	if(c[i] == false) {
    	p[pn++] = i;
        for(int j = i * i; j <= n; j += i) {
        	c[j] = true;
        }
   	}
}

안쪽 for문(j)는 N의 크기에 따라서, i+i 또는 i*2로 바꾸는게 좋다.(i가 백만인 경우 i*i는 범위를 넘어가기 때문에 정수 오버플로어가 일어날 수가 있다. 또한 이미 지워진게 또 지워져도 상관없기 때문)

 

에라토스테네스의 체로 문제를 풀경우 시간복잡도는 O(Nlog(logN))으로 거의 리니어한 타임, 즉 O(N)과 거의 같다.

 

 

5. 골든바흐의 추측(Goldbach's conjecture)

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

10^18이하의 수에서 참인 것이 증명되어 있으므로, 문제를 푸는 일반적인 경우에 참이다.

에라토스테네스의 체를 응용하여 풀이 가능하다.

 

 

6. 관련문제

 

소수구하기 : www.acmicpc.net/problem/1929

골드바흐의 추측 : www.acmicpc.net/problem/6588

풀이 및 코드

P[i] + ? = N을 검증.
N-P[i]가 소수인지 확인

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX = 1000000;
bool check[MAX+1];
int pn;
int prime[MAX];

int main(void) {
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(0);
	check[0] = check[1] = true;
	for (int i = 2; i <= MAX; ++i) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i+i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (true) {
		int n;
		cin >> n;
		if (n == 0) return 0;

		for (int i = 1; i <= pn; i ++) {
			if (check[n-prime[i]]==false) {
				cout<<n<<" = " << prime[i] << " + "<<n-prime[i]<<'\n';
				break;
			}
		}
	}

}

출력이 십만이 넘어가면 출력만으로도 시간제한을 넘어선다.

이경우 메인함수 안에 코드를 입력하여 해결 가능하다.

참고 //www.acmicpc.net/problem/15552

15552번: 빠른 A+B