백준을 풀다가 2609번, 최대공약수 / 최소공배수 구하는 알고리즘을 구현하는 것을 보았는데
굳이 for문이나 while 돌려 가며 브루트 포스를 하고 싶지 않아서...
더 빠른 방법이 있을까 하여 알고리즘을 찾아보았다.
최대공약수 (Greatest Common Divisor)
최대공약수 구할 땐, 유클리드 호제법을 이용한다.
x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리를 이용.
x % y = r
코드는 재귀함수로 구현하였으며, x나 y 어느 한쪽이 0이 되는 순간 다른 것을 리턴한다.
int GCD(int x, int y)
{
if (x == 0) return y;
else if (y == 0) return x;
else return GCD(y, x % y);
}참고로, Brute Force로 문제를 풀면 시간복잡도는 O(n)이 되는데, 유클리드 호제법으로 문제를 해결하면 시간복잡도는 O(log n)이 된다.
최소공배수 (Least Common Multiple)
최소공배수 = 두 자연수의 곱 / 최대공약수
이 모두를 코드로 하여 백준 2609를 풀면
#include <iostream>
using namespace std;
int GCD(int x, int y)
{
if (x == 0) return y;
else if (y == 0) return x;
else return GCD(y, x % y);
}
int main()
{
int x, y;
cin >> x >> y;
cout << GCD(x, y) << endl;
cout << x * y / GCD(x, y) << endl;
}참고
