유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다.

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

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

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

유클리드 호제법의 원리

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

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

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

[1934] 최소 공배수 구하기

[1850] 최대 공약수 구하기

[1033] 칵테일 만들기