[BK] 알고리즘 기초 - 수학 1

나머지 연산

(Modular Arithmetic)

- 데이터 저장 범위 때문에, 답을 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

- 나눗셈은 성립X (Modular inverse 구해야 함)

- (A-B) mod M = ( (A mod M) - (B mod M) + M ) mod M

* mod 연산한 결과가 음수가 나올 수도 있으므로

최대공약수

(Greatest Common Divisor, GCD)

- 유클리드 호제법(Euclidean algorithm)을 이용

- a를, b로 나눈 나머지를 r이라 하면 

GCD(a, b) = GCD(b, r)

- r이 0이면 그때 b가 최대 공약수

- 세 수의 최대공약수는 GCD(a,b,c) = GCD( GCD(a,b), c)

최소공배수

(Least Common Multiple, LCM)

- GCD를 응용해서 구할 수 있음

- a,b의 최대공약수 g에 대해 최소공배수 ; = g x (a/g) x (b/g)

진법 변환

(Base Conversion)

- 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될 때 까지 나머지를 구함

- B진법 수 N을 10진수로 바꾸려면 B^k를 곱하면서 더해가면 됨

- A진법을 B으로 바꾸려면 A진법 -> 10진법 -> B진법

소수

(Prime Number)

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

- N이 소수가 되려면 N>=2이고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안됨

- i <= N*N로 나누는 수 조건 검사

에라토스테네스의 체

- 1 ~ N 범위의 모든 소수를 구하는데 사용

(1) 2 ~ N까지 모든 수를 써놓음

(2) 아직 지워지지 않은 수 중 가장 작은 수 찾음

(3) 그 수는 소수

(4) 그 수의 배수를 모두 지움

소인수분해

(Prime Factorization)

- 정수 N을 소수의 곱으로 분해

- 소수를 구할 필요 없이 해결 가능

- N을 소인수분해 했을 때 나타날 수 있는 인수 중 가장 큰 값은 루트 N이기 때문에,

2 ~ 루트N까지 반복문으로 돌며 N을 나눌 수 없을 때까지 계속해서 나누면 됨

팩토리얼

- N! = 1 x 2 x ... x N

팩토리얼의 0의 개수

- N!을 소인수분해 했을 때 2, 5의 개수 이용

- 5의 개수가 항상 2의 개수보다 적기 때문에, 5의 개수만 구해도 됨

- N!의 0의 개수 = N/5 + N/5^2 + N/5^3 + ...

조합 0의 개수

- 2, 5의 개수 동시에 세야 함