[알고리즘] 정수론 : 유클리드 호제법(Euclidean Algorithm)

💡 유클리드 호제법이란?

유클리드 호제법은 두 수의 최대 공약수(GCD)를 구하는 효율적인 알고리즘입니다.
일반적으로 최대 공약수를 구할 때 소인수분해를 이용할 수 있지만, 유클리드 호제법을 사용하면 더욱 간단하게 해결할 수 있습니다.

유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법을 사용하면 좀 더 간단하게 구현 가능하다

---

💡 유클리드 호제법의 핵심 원리

이 알고리즘은 MOD(나머지 연산)을 기반으로 작동합니다.

MOD 연산: 두 수를 나눈 후 나머지를 구하는 연산

예) 10 MOD 4 = 2

---

🔢 유클리드 호제법 구현 과정

1️⃣ 두 수 중 더 큰 수를 작은 수로 나눈다.
2️⃣ MOD 연산(나머지 연산)을 수행한다.
3️⃣ 나머지를 이용해 같은 과정을 반복한다.
4️⃣ 나머지가 0이 되면, 나누는 수가 최대 공약수(GCD)가 된다.

---

📝 예제: 270과 192의 최대 공약수 구하기

gcd(270, 192)
270 % 192 = 78  
192 % 78  = 36  
78  % 36  = 6  
36  % 6   = 0  (종료)

➡️ 최대 공약수(GCD) = 6

---

⚒️ 유클리드 호제법의 장점

✔️ 빠르고 효율적 → O(log N)의 시간 복잡도
✔️ 소인수분해보다 간단한 구현 가능
✔️ 재귀 및 반복문으로 쉽게 구현 가능

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!