최대공약수를 구하는데에 많이 사용되는 알고리즘입니다.
해당 알고리즘을 활용하는 백준 문제를 마주하게되어 어떻게 해결하였는지 해설하는 김에 알고리즘에 대한 설명도 추가하려고 글을 작성하였습니다.
https://www.acmicpc.net/problem/2609
유클리드 호제법을 사용하지 않을 경우, 아마 다음과 같은 알고리즘을 통하여 최대 공약수를 구할 수 있을 것입니다.
// 두 정수 중 큰 값을 num1, 작은 값을 num2라고 가정하겠습니다.
for(int i = 1; i <= num2; i++) {
if(num1 % i == 0 && num2 % i == 0) {
gcd = i;
}
}물론 이러한 방식으로도 최대공약수를 구할 수 있으나, O(N)이라는 시간 복잡도를 가집니다.
그러나, 유클리드 호제법을 활용하는 경우에는 O(log N)이라는 시간 복잡도를 통하여 최대 공약수를 구할 수 있습니다.
두 정수가 주어졌을 때, 큰 정수를 A, 작은 정수를 B라고 하겠습니다.
만약 A % B 의 값이 0인 경우에는 B가 최대공약수가 되지만, 그렇지 않은 경우에는 B를 A에 대입하고, A % B를 B에 대입하여 동일한 연산을 수행하는 것이 유클리드의 호제법입니다.
이와 같은 연산을 통하여 우리는 두 정수의 최대공약수를 구할 수 있으며, 최소공배수의 경우에는 두 수의 곱을 최대공약수로 나눌 경우 구할 수 있습니다.
// 최대 공약수를 구하는 함수
public static int getGCD(int big, int small) {
if(big % small == 0) return small;
return getGCD(small, big % small);
}
// 최소공배수를 구하는 함수
public static int getLCM(int num1, int num2, int gcd) {
return num1 * num2 / gcd;
}
아래가 유클리드 호제법을 활용하여 문제를 푼 경우이고, 위가 for문을 활용하여 문제를 푼 경우입니다.
조금이긴해도 유클리드 호제법을 활용하여 문제를 푼 경우가 더 빠른 것을 확인할 수 있습니다.
