[C++] 두 수의 최대공약수와 최소공배수 (유클리드 호제법)

[C++] 최대공약수와 최소공배수와의 관계 (유클리드 호제법)

 

알고리즘 문제를 풀다보면, 두 수의 최대공약수나 최소공배수가 필요한 상황이 생긴다. 이러한 상황에서는, 최대공약수만 구하더라도 최소공배수를 알 수 있기 때문에 최소공배수를 구하는 법만 알고있으면 된다.  최소공배수를 구하는 방법은 여러가지가 있지만, 컴퓨터 알고리즘에는 유클리드 호제법으로 구하는 것이 가장 빠르고 많이 사용되는 방식이다.

 

#include <iostream>

using namespace std;
int gcd(int a, int b) {
	int r;
	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{
	int a, b;
	cin >> a >> b;
	cout <<"두 수의 최대공약수는 : "<< gcd(a, b)<<" 입니다" << endl;
	cout << "두 수의 최소공배수는 : " << (a*b)/gcd(a, b) << " 입니다" << endl;
}

C++ 코드.

예제로 12와 8의 최대공약수를 구한다고 가정하자.

위 프로그램은 재귀적으로 구성되어 있지는 않지만 아래와 같이 작동한다고 생각해도 무방하다.

GCD(12, 8) >>> GCD(8, 12%8) ==GCD(8,4) >>> GCD(4, 8%4) == GCD(4,0) == 4

 

유클리드 호제법에 따르면 a라는 수와 b라는 수가 있을 때 a와 b의 최대공약수(Greatest Common Divisor) gcd(a,b)는 gcd(b, a%b)라고 표현할 수 있다. gcd(a,b)를 a가 b보다 더 크다고 가정하면 q라고 가정했을 때, a = a1*q 로 b = b1*q로 표현 가능하다. 만약 a-b를 하게되면 a-b = (a1-b1)*q가 된다. a1-b1는, a가 b보다 크다고 가정했기 때문에 서로소 관계이고 따라서 a-b는 반드시 a보다 작은 값이 된다. 그리고 가장 중요한 점은 a-b가 q라는 최소공배수를 포함하고 있다는 사실이다.

따라서 a와 b의 최대공약수를 구하는 문제가 b와 a-b 사이의 최대공약수배수를 구하는 문제로 치환하여 해결할 수 있다.

코드를 살펴보면, a-b가 아니라 a%b로 하였는데 이유는 a-b를 여러번 하는 것과 a%b를 하는 것은 같은 연산이고, 따라서 a%b를 하는 것이 훨씬 빠르기 때문이다. b가 0이 될 때 while문을 빠져나가는데, 이 때 a값이 우리가 구하고자 하는 최대공약수 이다. 수가 모두 소수라면 최대공약수는 1로 출력이 된다.

<참고>

GCD(12,8) >>>  GCD(12-8, 8) >>>  GCD(4, 8) >>> GCD(8, 4) >> GCD(4,4) >>> GCD(0,4) > GCD(4, 0) == 4

매번 스탭마다 a와 b의 대소비교를 하고 b가 더 크다면, a와 b를 swap해줘야 한다. 그리고 Step수가 길다.

GCD(12, 8) >>> GCD(8, 12%8) ==GCD(8,4) >>> GCD(4, 8%4) == GCD(4,0) == 4

그러나 위 처럼 %연산을 하면 두번의 Step만에 구할 수 있다. 또한 왼쪽에 들어가는 값은 항상 오른 쪽 값보다 크기 때문에 크기비교를 해줄 필요가 없다. (나머지 연산의 특징)

 

최대공약수를 구했다면, 최소공배수(LCM)는 구한 것이나 다름없다. 왜냐하면 최대공약수와 최소공배수 사이에는 다음과 같은 관계가 성립하기 때문이다. 

lcm(a*b)*gcd(a,b) = a*b

 

 

위식을 조금 변형해서, 최종적으로 최소공배수 lcm(a,b)는 a와 b를 곱한 값에 gcd(a,b)를 나누어 주면 된다.