유클리드 호제법 (euclidean-algorithm)

 

코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다.

 

최대공약수를 구하는 가장 기본적인 방법은 두 수를 소인수 분해한 뒤, 공통된 소수들의 곱을 구하는 것이다.
하지만 이 방법은 구현이 번거롭고, 큰 수에 대해서는 비효율적이다.

 

이를 훨씬 간단하고 빠르게 구할 수 있는 방법이 바로 유클리드 호제법(Euclidean Algorithm) 이다.

이번 글에서는 유클리드 호제법의 원리와 동작 과정, 그리고 왜 이 방법이 효율적인지 정리해보려고 한다. ✍️

 

 

---

 

 

유클리드 호제법이란?

유클리드 호제법은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.

이 알고리즘의 핵심 아이디어는 다음과 같다.

두 수 A와 B에 대해
A를 B로 나눈 나머지를 R이라고 할 때,
gcd(A, B) = gcd(B, R) 이다.

 

즉, 최대공약수는 나머지를 이용해 계속 줄여나갈 수 있다는 뜻이다. 🔁

 

 

---

 

 

핵심 개념: MOD 연산

유클리드 호제법을 이해하려면 먼저 MOD 연산(나머지 연산) 을 이해해야 한다.

A % B = A를 B로 나눈 나머지

이 나머지 연산이 최대공약수를 구하는 데 핵심 역할을 한다.

 

왜냐하면,

• A와 B의 공약수는
• B와 (A % B)의 공약수와 동일하기 때문이다.

이 성질 덕분에 숫자를 점점 줄이면서 최대공약수를 구할 수 있다.

 

 

---

 

 

유클리드 호제법의 동작 과정 🔁

유클리드 호제법은 다음 3단계를 반복한다.

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
3. 단계 2번을 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다,

 

 

---

 

 

시간 복잡도 ⏰

유클리드 호제법의 시간 복잡도는 아래와 같다.

O(log N)

 

나머지 연산을 할 때마다 숫자가 급격히 줄어들기 때문에 매우 효율적인 알고리즘으로 알려져 있다.

그래서 큰 수에 대해서도 빠르게 최대공약수를 구할 수 있다.