알고리즘 [정수론] - 유클리드 호제법

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

---

유클리드 호제법의 핵심 이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해해야 한다.

연산	기능	예제
MOD	두 값을 나눈 나머지를 구하는 연산	10 MOD 4 = 2 (10 % 4 = 2)

MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다.

MOD 연산으로 구현하는 유클리드 호제법

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

---

유클리드 호제법의 원리 이해하기

다음은 270과 192의 최대 공약수를 유클리드 호제법으로 찾아보는 그림이다.

---

• Do it! 알고리즘 코딩테스트 자바 편