이걸 직접적으로 물어본 경험은 없지만, 최대공약수와 최소공배수를 구하는 알고리즘을 실제로 작성해본 적 없는 분들이 의외로 많음을 알았습니다. 여기서는 유클리드 호제법을 이용하여, 최대공약수(GCD)와 최소공배수(LCM)을 한 줄로 코딩하는 방법을 설명하겠습니다.
먼저 유클리드 호제법은 무려 기원전 300년 경에 유클리드 원론에 쓰인 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘입니다. 이 호제법의 핵심은 어떤 임의의 수 $a$, $b$에 대해 $a \mod b = r$ 이라고 한다면, $gcd(a,b) = gcd(b,r)$ 이 성립한다는 점을 이용합니다. 이렇게 반복하면서 최종적으로 나머지가 0이 되는 순간 그 나누는 수가 최대공약수가 됩니다. 여기서는 수학적 증명에 대해서는 다루지 않겠습니다. 수학적 증명은 여기서 읽어보실 수 있습니다.
이제 이것을 소스코드로 구현을 해야 합니다. 먼저 말 그대로 소스코드로 이 내용을 옮겨봅시다.
int gcd(int a, int b)
{
while (1)
{
int r = a%b;
/*나머지가 0이라면*/
if (r == 0)
return b;
/*gcd(a,b) = gcd(b,r)*/
a = b;
b = r;
}
}
제목에서 말했다시피 우리는 이 소스를 1줄로 압축할 것입니다. 압축하는 과정에서 위의 소스를 재귀함수의 형태로 변경하겠습니다. 즉, r=a%b 부분을 만들어 검사하는 대신, b의 값을 파라미터 a의 위치에, a%b 을 파라미터 b의 위치로 넘겨주어, 나머지가 0이 될 때까지를 체크합니다. 이럴 경우 소스코드가 다음과 같이 바뀝니다.
int gcd(int a, int b)
{
if (b == 0) return a;
else return gcd(b, a%b);
}
여기서 깨끗한 문법은 아니지만, 다음과 같은 작업을 거쳐 최종적으로 1줄로 최대공약수를 구할 수 있습니다.
int gcd(int a, int b)
{
return !b ? a : gcd(b,a%b);
}
다소 길었던 소스가 1줄로 압축되었음을 알 수 있습니다. 최소공배수는 어떻게 구할 까요? 최소공배수는 두 수의 공통적인 배수이므로, 두 개의 수를 곱한 다음, 최대공약수로 나눈 것이 항상 답이 됨을 알 수 있습니다. 그러므로 이 소스 역시 1줄로 짤 수 있습니다.
int lcm(int a, int b)
{
return a*b/gcd(a,b);
}
이 2가지의 원리를 이해하고 소스를 외운(?)다면, 이것들을 이용한 문제를 아주 쉽게 해결할 수 있을 것입니다. 소스코드에는 예제 소스를 첨부하겠습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
using namespace std;
int gcd(int a, int b){return !b ? a : gcd(b, a%b);}
int lcm(int a, int b) { return a*b / gcd(a, b); }
int main()
{
cout << gcd(10, 24) << "\n" << lcm(22,66);
}