[정수론] 유클리드 호제 법 - 두 수의 최대 공약수

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현 할 수 있지만

유클리드 호제법은 조금 더 간단한 방법을 제시한다.

 

<핵심 이론>

먼저 MOD 연산을 이해

→ MOD 연산은 유클리드 호제법에서 최대 공약수를 구하는 핵심 이론

 

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

 

 

아래 3단계로 진행한다.

 

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

 

GCD : Greatest Common Divisor로 최대 공약수의 줄임말

 

gcd(270, 192)

270 % 192 = 78　　　　　　 ←　① 큰 수에서 작은 수로 MOD 연산 수행

　　　　↓　↓

　　　192 % 78 = 36　　　　←　② 전 단계 에서의 작은 수를 큰 수로, 연산 결과를 작은 수로 다시 설정 후 

　　　　　　 ↓ 　↓ 　　　　　　　　단계 ① 재진행

　　　　　　78 % 36 = 6　　←　③ MOD 연산 결괏값이 0이 나오면 그 연산의 작은 수를 최대 공약수로 선택

　　　　　　　　   ↓ 　↓　↙

　　　　　　　　  36 % 6 = 0

 

유클리드 호제법은 코딩테스트에서 recursive function 즉, 재귀 형태로 구현한다.