[알고리즘] 최대공약수와 최소공배수 - 간단하게 구현해보기 (+ 유클리드 호제법 알고리즘) (C++)

 

<1> 최대공약수란 무엇인가?

 

최대공약수는 초등학교 수학 시간에 배우는 내용으로, 아마 이 글을 보시는 여러분이라면 이미 아시겠지만, 그 개념을 한 번 더 짚고 넘어가보자.

 

쉬운 이해를 위해 실제 정의가 아닌 초등학교 교과서에 제시된 내용을 참고하였다.

 

 

n의 약수 : n을 나누어 떨어지게 하는 수

 

a, b의 공약수 : a와 b의 공통된 약수

 

a, b의 최대공약수 : a와 b의 공통된 약수 중 가장 큰 수

 

 

 

이 개념을 이용하여 반복문으로 다음과 같이 최대공약수를 구하는 함수 코드를 쓸 수 있다.

#include <iostream>
#include <algorithm>

// 최대공약수를 계산하는 함수 
long getBCD (long a, long b)
{
	for(int div = min(a, b); div > 0; div--)
    {
    	if((a % div == 0) && (b % div == 0))
        // div : 공약수
        // 최초의 공약수 -> 최대공약수
        	return div;
    }
}

 

이 알고리즘을 개선해, 더 간단한 복잡도로 최대공약수를 구하는 코드가 있다.

 

최대공약수를 구하는 다른 방법으로 '유클리드 호제법 알고리즘'에 대해 알아보자.

 

아마 전공자라면, 학과 수업에서 한 번은 다뤄봤을 내용일 것이다.

 

 

---

 

<2> 유클리드 호제법 알고리즘

 

'유클리드 호제법 알고리즘'은 '유클리드 호제법'을 통해 최대공약수를 구하는 알고리즘으로

 

인류 최초의 알고리즘이라고 한다. (그렇구나)

 

그 내용은 다음과 같다.

 

 

2개의 자연수(또는 정식) A, B에 대해서 A를 B로 나눈 나머지를 R이라 하면 (단, A > B)

 

A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (유클리드 호제법)

 

 

(수식으로 증명)

 

A = BQ + R  ->  gcd(A, B) = G이면,

 

A = Ga, B = Gb (a, b는 서로소)

 

Ga = GbQ + R

 

R = G(a - bQ)

 

gcd(B, R) = G

 

 

 

 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

 

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. (유클리드 호제법 알고리즘)

 

 

(수식으로 설명)

 

A = B(Q1) + (R1),  gcd(A, B) = G

 

B = R1(Q2) + (R2), gcd(B, R1) = G

 

R1 = R2(Q3) + (R3), gcd(R1, R2) = G

 

...

 

R(n-1) = Rn(Q(n+1)), gcd(R(n-1), Rn) = G

 

 

gcd(A, B) = gcd(B, R1) = ... = gcd(R(n-1), Rn) = G

​

 

 

 

 

두 정수 A, B에 대하여

 

A의 약수가 B라면 ( A = BQ ), A와 B의 최대공약수는 B가 된다.

 

그렇지 않다면 ( A = BQ + R (R!=0) ), 'A와 B의 최대 공약수' == 'B와 (A%B)의 최대공약수' 이다.

 

 

즉, (A % B) != 0 이라면 gcd(A, B) == gcd (B, A%B)이고

 

(A % B) == 0 이면, gcd(A, B) == B인것이다.

 

 

이 알고리즘을 이용해 최대공약수를 구하는 코드를 작성하면 다음과 같다.

 

long getGCD(long a, long b)
{
	long temp = a % b;
	
	while (temp != 0)
	{
		a = b;
		b = temp;
		temp = a % b;
	}
	
	return b;
}

이 알고리즘의 핵심은, (A % B) != 0 일 때 gcd(A, B) == gcd(B, A%B)임을 이용해

 

(A % B)값이 0이 될 때까지 나머지를 계산하는 과정을 반복하는 것이다.

 

참고로 A < B일 때도 이 알고리즘은 성립한다.

 

---

 

<3> 최소공배수 구현

 

두 정수 A, B의 최소공배수는 'A의 배수이면서 동시에 B의 배수가 되는 최소의 수'이다.

 

역시 반복문으로 다음과 같이 최소공배수를 구하는 함수 코드를 쓸 수 있다.

 

#include <iostream>
#include <algorithm>

// 최소공배수를 계산하는 함수 
long getLCM (long a, long b)
{
	for(int mul = max(a, b); mul <= a * b; mul++)
    {
    	if((mul % a == 0) && (mul % b == 0))
        // mul : 공배수
        // 최초의 공배수 -> 최소공배수
        	return mul;
    }
}

만일 A, B의 최대공약수를 안다면, 이 알고리즘 역시 더 간단한 복잡도 개선할 수 있다.

 

최소공배수에는 다음과 같은 성질이 있다.

 

 

lcm(A, B) = AB / gcd(A, B)

 

 

(간단한 증명)

 

위 최대공약수에서 이용한 수식을 재탕하자.

 

A = BQ + R

 

gcd(A, B) = G,  A = Ga, B = Gb (a, b는 서로소)

 

이 때, lcm(A, B) = Gab

 

즉, Gab = AB / G

 

Gab = (Ga)(Gb) / G

 

Gab = Gab

 

 

 

 

A, B의 최대공약수 값과 이 성질을 이용해 코드를 개선해보자.

// 최대공약수 구하는 함수
long getGCD(long a, long b)
{
	long temp = a % b;
	
	while (temp != 0)
	{
		a = b;
		b = temp;
		temp = a % b;
	}
	
	return b;
}


// 최소공배수 구하는 함수
long long getLCM(long long a, long long b)
{
	return a * b / getGCD(a, b);
}

반복문을 쓸 필요도 없이 딱 한 줄의 함수로 구할 수 있다.