[기초] 알고리즘 수학1

 

 

 

알고리즘을 풀 때 필요한 수학 내용을 다루고자 합니다.

 

 

1. 나머지 연산 (Modular Arthmetic)

 

첫번째로 자주 사용하는 내용입니다.

 

 

(A+B) % C = ( (A%C) + (B%C) ) % C

 

 

 

A+B에서 나머지 연산으로 위와 같은 식이 성립합니다.

증명은 아래 링크 참고

 

모듈러 연산의 성질과 증명

 

다이나믹 프로그래밍 문제 중에 경우의 수를 구하는 문제일 때

경우의 수가 너무 큰 경우 또는 정수 범위를 넘어가는 경우

 

이 연산을 이용하여 풀이가 가능합니다.

 

 

 

- 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다.

 

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

- (AxB) mod M = ( (A mod M) x (B mob M) ) mod M

- 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 함)

 

- 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.

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

 

---

2. 최대공약수 (Greatest Common Divisor)

 

- 최대공약수는 줄여서 GCD라고 쓴다.

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

- 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(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;
    }
}

이렇게 최대공약수를 코드로 구하면 시간 복잡도는 O(N)

 

좀 더 빠르게 구하는 방법은 유클리드 호제법을 이용하는 방법이 있습니다.

 

 

 

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

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

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;
}

//분모가 0이 아닐때 간단히

int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}

 

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

 

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

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

 

---

 

3. 최소공배수 (Least Common Multiple)

 

- 최소공배수는 줄여서 LCM이라고 한다.

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

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

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

- 최소공배수 l = g * (a / g) * (b / g)이다.

 

그래서 

L x G = A x B이므로

최소공배수 L은 L = (A x B) / G

// 최대공약수

int gcd(int a, int b){ 
	return b ? gcd(b, a%b) : a;
}

// 최소공배수

int lcm(int a, int b){ 
	return a * b / gcd(a, b);
}

 

 

이때 조심할 점은 최소공배수는 두 수보다 커질 수 있으므로

수의 범위를 확인하여  A, B가 int 범위 안에 있어서 최소공배수는 int범위를 넘어갈 수 있다.