유클리드 호제법으로 최대공약수(GCD) 구하기

유클리드 호제법으로 최대공약수 구하기

오늘은 두 정수의 최대공약수(GCD)를 가장 효율적으로 구하는 방법인 유클리드 호제법(Euclidean Algorithm)을 소개합니다.

이 알고리즘은 단순 반복 방식보다 훨씬 빠르고 구현이 간단하며, 실제로 대부분의 프로그래밍 언어 내부에서도 사용되는 고전적이면서 강력한 기법입니다.

 

이 글을 통해 다음 내용을 이해할 수 있어요.

• 유클리드 호제법이 동작하는 직관적 원리
• 반복문과 재귀를 활용한 자바 구현 예제
• 단순 반복 방식과 비교했을 때의 차이점과 장점

 

기존 방식: 반복문으로 공약수 찾기

---

가장 단순한 접근은 두 수 중 작은 값까지 반복문을 돌며 공약수를 찾는 방식입니다.

public int getGreatestCommonDivisor(int num1, int num2) {
    int little = num1 < num2 ? num1 : num2;
    int gcd = 0;
    for(int i = 1; i <= little; i++) {
        if(num1 % i == 0 && num2 % i == 0) gcd = i;
    }
    return gcd;
}

직관적이고 이해하기 쉽지만, 두 수가 커질수록 반복 횟수가 많아져 효율이 크게 떨어진다는 한계가 있습니다.

 

유클리드 호제법(Euclidean Algorithm)이란?

---

유클리드 호제법

유클리드 호제법은 다음 성질에 기반한 최대공약수(GCD) 계산 알고리즘입니다.

 

두 정수 a, b(a > b)에 대해

• a = bq + r 이라면
• gcd(a, b) = gcd(b, r)
• 그리고 r = 0이 되는 순간, b가 최대공약수입니다.

핵심은 한 문장으로 요약할 수 있습니다.

 

큰 수를 작은 수로 나누고, 그 나머지를 다시 작은 수로 나누는 과정을 반복하면 마지막 남는 값이 최대공약수이다.

 

이게 어떻게 가능한가?

---

a = bq + r 이라고 표현할 수 있을 때,

• a와 b의 공약수는 r도 나누어야 합니다.
  → r = a − bq 이므로, a와 b를 모두 나누는 수라면 r 역시 나눌 수 있습니다.
• 반대로, b와 r의 공약수는 a도 나눌 수 있습니다.
  → a = bq + r 이므로, b와 r을 모두 나누는 수라면 a 역시 나눌 수 있습니다.

결국 다음 관계가 성립하게 되요.

 

a와 b의 공약수 = b와 r의 공약수

 

따라서 이 과정을 r = 0이 될 때까지 반복하면,
마지막으로 남는 값(b)이 최대공약수(GCD)가 됩니다.

 

자바로 구현해보기

---

유클리드 호제법은 반복문과 재귀 두 방식 모두로 간단하게 구현할 수 있습니다.

 

반복문을 사용한 방법

public int euclidean(int num1, int num2) {
    while (num2 != 0) {
        int r = num1 % num2;
        num1 = num2;
        num2 = r;
    }
    return num1;
}

 

재귀를 사용한 방법

public int euclidean(int num1, int num2) {
    if (num2 == 0) return num1;
    return euclidean(num2, num1 % num2);
}

 

두 방식 모두 동일한 로직을 따르며, 최대공약수가 num2가 0이 되는 시점의 num1이라는 점을 그대로 구현하고 있습니다.

 

시간 복잡도와 주의점

---

유클리드 호제법은 대부분의 경우 O(log n) 에 가까운 매우 빠른 알고리즘입니다.
입력 값이 커져도 반복 횟수가 급격히 증가하지 않기 때문에, 일반적인 프로그래밍 문제에서는 사실상 가장 효율적인 GCD 계산 방식으로 평가됩니다.

 

이론적으로는 특정 큰 수 조합에서 실행 횟수가 다소 늘어날 수 있으며, 매우 큰 정수 연산이 필요한 경우에는 확장 유클리드 알고리즘이나 준선형 알고리즘이 활용되기도 합니다.

 

그러나 실무·코딩 테스트·일반 개발 환경에서는 유클리드 호제법이 가장 빠르고 안정적인 선택입니다.

 

분수 연산에서도 유클리드 호제법을 활용하면
코드를 더 간결하게 만들 수 있고 계산 역시 훨씬 빨라집니다.

 

앞으로도 흥미롭고 실용적인 알고리즘을 발견할 때마다
계속 소개해 보겠습니다!