최대공약수와 최소공배수

이번 포스트에서는 최대공약수와 최소공배수를 구하는 알고리즘에 대해 알아보자.
알고리즘이라고 하긴 뭐하지만.. 알고리즘이다.

최대공약수 (Great Common Divisor)

최대공약수는 줄여서 GCD라고 부른다.

두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 이때, 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.

최대공약수를 구하는 방법은 두 가지가 있다.

1. 2부터 min(A,B)까지 가능한 모든 정수로 나누어 보는 방법
2. 유클리드 호제법(Euclidean algorithm)을 이용하는 방법

각 방법에 대하여 알아보도록 하자.

1. 가능한 경우 다 해보기

두 수 A와 B의 최대공약수의 후보가 될 수 있는 수는 2이상 min(A,B) 이하이다. 어떤 수로 두 수를 나누었을 때, 두 수의 나머지가 모두 0이면 그 수는 A와 B의 공약수라고 할 수 있다.

int GCD(int a, int b)
{
	int gcd = 1;
    
    for(int i = 2; i <= min(a,b); i++)
    {
    	if(a % i == 0 && b % i == 0)
        	g = i;
    }
    
    return gcd;
}

시간복잡도

시간복잡도는 $O(N)$이라고 할 수 있다.

2. Euclidean algorithm 이용하기

이름은 거창하다. 어디서 많이 들어본 유클리드 선생님이다.

뭐 별다른건 없고, GCD를 구하는 알고리즘 중 하나일 뿐이다.

A를 B로 나눈 나머지를 R이라고 했을 때, GCD(A,B) == GCD(B, R) 이라는 수학적 지식을 이용하는 알고리즘이다. (증명은 여기에서..) R이 0이되면 그 때의 B가 A와 B의 최대 공약수이다.

재귀함수로 유클리드 알고리즘을 구현하면 다음과 같다.

int GCD(int a, int b)
{
	if(b == 0)
    	return a;
    
    return GCD(b, a%b);
}

재귀함수에서 재귀 call(?)뭐라고부르지이 한번뿐인 재귀함수는 모두 비재귀함수로 구현할 수 있다.

비재귀함수로 유클리드 알고리즘을 구현하면 다음과 같다.

int GCD(int a, int b)
{
	int gcd = 1;
    
    while(b != 0)
    {
    	int r = a%b;
        a = b;
        b = r;
    }
    
    gcd = a;
    
    return gcd;
}

최소공배수 (Least Common Multiple)

최소공배수는 줄여서 LCM이라고 부른다.

두 수 A와 B의 LCM은 A와 B의 GCD를 응용해서 구할 수 있다.

$LCM = GCD * \frac A {GCD} * \frac B {GCD}$

이때, LCM은 A와 B를 곱하게 되면서 수가 커질 수 있기 때문에 수의 범위 확인이 반드시 필요하다.

int LCM(int a, int b)
{
	int g = GCD(a, b);
    
    return g * (a / g) * (b / g);
}