수학 관련

최근 코테에서 자주 나오는 부분이 모듈러 연산, 최대 공약수, 소수다.

자주 풀어보지 않기 때문에 막상 나오면 헤매는 경우가 잦기 때문에 오늘 정리하려고 한다.

아래의 정리는 백준의 강의를 듣고 감명받은 점들과 나의 생각을 정리해서 적어놓았다.

모듈러 연산(나머지 연산, modular)

말 자체가 처음에는 와닿지 않는 용어지만 % 기호를 보면 한 번에 이해하기 쉽다.

10 % 7 => 3
6 % 7 => 6
0 % 7 => 0
7 % 7 => 0

어떤 수를 7로 모듈러 연산한다고 하면 나올 수 있는 경우의 수는 0 ~ 6 다.

아무리 큰 수가 와도 저 안에 머무른다는 소리다.

 

응용

어떤 물고기가 (1,1) 에서 5 x 5 격자 안에서 움직인다고 할 때 5의 속력으로 동쪽으로 이동한다고 하면?

(1,1) -> (1,2) -> (1,3) -> (1,4) -> (1,5) -> (1,1)

한 칸 씩 이동한다고 구현하면 위와 같이 5번을 다 계산하지만 모듈러 연산을 쓰면 다음과 같이 편하게 압축(최소화)할 수 있다.

y축(열)만 보면 (1 + 5) % 5 = 1로 쉽게 압축할 수 있다.

 

음수는 예외적으로 뒤에다가 나머지 연산하는 수를 붙이지만 덧셈과 곱셈은 다음과 같이 풀어서 사용이 가능하다.

단, 나누기는 제외

(a + b) % c = (a % c + b % c) % c
(a * b) % c = (a % c * b % c) % c
(a - b) % c = (a % c - b % c + c) % c

이렇게 풀어서 사용하는 경우는 오버플로우를 방지하기 위해서다.

 

최대공약수 GCD( Greatest Common Divisor)

정의는 두 수 a와 b의 공통된 약수 중에서 가장 큰 정수다.

최대공약수를 빠르게 구하는 알고리즘은 유클리드 호제법이다.

반복문보다는 재귀로 구현하는 게 훨씬 기억하기 쉽고 실수를 최대한으로 줄일 수 있다.

시간 복잡도는 매 턴마다 b로 나누기 때문에 O(lgB) = O(lgN)

//재귀 구현
int gcd(int a, int b) {
	if(b == 0) return a;
    return gcd(b, a%b);
}

//반복문 구현
int gcd(int a, int b) {
	while(b != 0) {
    	int r = a % b;
        a = b;
        b = r;
    }
}

응용

최대공약수를 구할 수 있으면 최소공배수도 쉽게 구할 수 있다.

중간중간에 나눠주는 이유는 오버플로우 방지

//g: 최대공약수
int lcm(int a, int b, int g) {
	return g * (a / g) * (b / g);
}

소수

정의는 약수가 1과 자기 자신밖에 없는 수를 소수라고 한다.

 

어떤 수가 소수인지 아닌지 판별하는 방법

판별하는 방법은 그 수를 n이라고 하면 2부터 sqrt(n)까지 나누어 떨어지면 그 수는 소수가 아니라는 방법을 이용해서 구현한다.

보통은 루트는 정수로 떨어지지 않기 때문에 정수로 떨어트리기 위해서 양변을 제곱하는 형태로 취하는 것이 좋다고 한다.

2 <= i <= sqrt(n)
4 <= i * i <= n

시간 복잡도 O(sqrt(N))

bool isPrime(int n) {
	if(n < 2) return false;
    for(int i = 2; i * i <= n; i++) {
    	if(n % i == 0) return false;
    }
    return true;
}

대량의 소수를 빠르게 구하는 방법 => 에라토스테네스의 체

이 방법은 다음과 같은 방법으로 소수를 판별한다.

2는 소수이고, 2의 배수는 모두 지운다.

3은 소수이고, 3의 배수는 모두 지운다.

5는 소수이고, 5의 배수는 모두 지운다.

....

지워진 수는 소수가 아니고 남아있는 수가 소수라는 뜻이다.

시간 복잡도 O(NlglgN)

int prime[100];  // 소수 저장
int pn = 0;      // 소수의 개수
bool check[101]; // 지웠다면 true, 아니라면 false
int n = 100;

for(int i = 2; i <= n; i++) {
	//2는 냅두고,
	if(check[i] == false) {
    	//소수를 저장하고 싶으면
    	prime[pn++] = i;
    	//2의 배수는 모두 지운다.
    	for(int j = i + i; j <= n; j += i) {
        	check[j] = true;
        }
    }
}

자주 자주 나오는 문제의 유형은 아니지만 꼭 기억해두자.

 

연습문제

소수 찾기

소수 구하기

나머지

최대공약수와 최소공배수

최소공배수

GCD 합

골드바흐의 추측