정수론 : 유클리드 호제법

유클리드 호제법

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

유클리드 호제법의 핵심 이론
유클리드 호재법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다.

MOD 연산 : 두 값을 나눈 나머지를 구하는 연산

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

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


*최대 공약수를 구하는 연산은 일반적으로 gcd로 정의.

 

gcd

관련 문제

1934	최소공배수	성공	34551	73925	55.946%
1850	최대공약수		6983	26024	35.061%
1033	칵테일		1307	5560	33.547%

 

책 <Do It! 알고리즘 코딩테스트>_김종관 지음, 이지스퍼블리싱 출판사

학교 알고리즘 수업 강의자료 등 여러 자료 참고해서 공부함.