[Algorithm] day3. Basic Math

Basic Math

모듈로 연산과 나눗셈 정리

• 모듈로 연산 (Modulo Operation)
  어떤 수를 m으로 나눠 그 나머지를 구하는 연산

• 나눗셈 정리 (Division Theorem)
  임의의 정수를 0이 아닌 정수로 나눈 몫과 나머지는 유일하다.
  m = n * q + r (위를 만족하는 정수 q, r은)

• 합동식
  a|b : b는 a로 나누어 떨어진다. (= b%a는 0이라는 뜻과 같다.)

최대공약수와 최소공배수

최대공약수(gcd)
int gdc(int a, int b) { return b ? gcd(b, a%b) : a; }

최소공배수(lcm)
int lcm(int a, int b) { return a / gcd(a, b) * b; }

유클리드 호제법

두 자연수 a, b의 최대공약수를 구하기

두 자연수 a, b → a를 b로 나눈 나머지 r
gcd(a,b) = gdd(b,r)

시간복잡도는 O(loga) 이다.

거듭제곱

integer overflow 때문에 모듈러를 취한다.

거듭제곱을 O(logn)로 구하는 방식을 분할 정복을 이용한 거듭제곱이다.

• x가 짝수 → a^x = a^(x/2) * a^(x/2)
• x가 홀수 → a^x = a^(x/2) a^(x/2) a

int m;
int fpow(int a, int x) {
	if (x == 0) return 1;
    int ret = fpow(a, x/2);
    ret = ret * ret % m;
    if (x % 2) ret = ret * a % m;
    return ret;
}

소수판정

양수 N이 주어졌을 때, N이 소수이면 1, 소수가 아니면 0을 반환하기

• N보다 작은 수로 나누기
  O(N) → O(N^2)

bool isPrime(int N) {
	for (int i = 2; i < N; i++)
    	if (N % i == 0) return 0;
    return 1;
}

• N^(1/2)보다 작거나 같은 수로 나누기
  O(N^(1/2)) → O(N * N^(1/2)) [이때, integer overflow 조심!!]

bool isPrime(int N) {
	for (int i = 2; i * i <= N; i++)
    	if (N % i == 0) return 0;
    return 1;
}

시간을 더 줄이려면 O(Nlog(logN))인 에라토스체네스의 체를 사용하면 된다.

에라토스체네스의 체

전처리 : O(Nlog(logN))
소수 판정 : O(1)
시간은 빠르지만, 공간적으로 손해이다.

1부터 n까지의 소수를 모두 찾는다.

• 2는 소수, 2의 배수는 모두 제거
• 3은 소수, 3의 배수는 모두 제거
• 4는 이미 제거 됨
• 5는 소수, 5의 배수를 모두 제거
  → 이 과정을 계속 반복

isPrime = [True for i in range(n+1)]

for i in range(2, n + 1):
    if isPrime[i] == True:
        j = 2
        while i * j <= n: # 소수인 수의 배수들은 다 False 처리
            isPrime[i*j] = False
            j += 1