유클리드 호제법이란?
유클리드 호제법은 가장 오래된 알고리즘 중 하나로, 기원전 300년경 그리스 수학자 유클리드가 정리한 방법입니다. 두 정수의 최대공약수(GCD), 즉 두 수를 모두 나누어떨어지게 하는 가장 큰 수를 찾아 줍니다. 이 계산기는 음이 아닌 두 정수에 알고리즘을 적용하며, 최소공배수(LCM)까지 함께 알려 드립니다.
사용 방법
a와 b 입력란에 두 수를 넣고 실행하세요. 최대공약수(GCD)가 메인 결과로, 최소공배수(LCM)가 보조 결과로 표시됩니다. 순서는 상관없습니다 — \(\gcd(48, 36)\)과 \(\gcd(36, 48)\)은 동일합니다. 음수를 입력하면 절댓값으로 처리되며, 한 수가 0이면 GCD는 다른 수가 됩니다.
공식 풀이
이 알고리즘은 간단한 통찰에서 출발합니다. a와 b의 공약수는 그 나머지인 a mod b도 나누어떨어지게 한다는 점입니다. 그래서 더 큰 수를 나머지로 계속 바꿔 나갑니다.
$$\gcd(a, b) = \gcd(b,\, a \bmod b)$$ 그리고 기저 조건은 $$\gcd(a, 0) = a$$ 입니다.
매 단계마다 수가 빠르게 줄어들기 때문에, 아주 큰 값이라도 몇 번의 반복만으로 답이 나옵니다. LCM은 $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$ 로 계산합니다.
예제 풀이
\(\gcd(48, 36)\)을 구해 봅시다.
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$ $$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$
따라서 GCD는 12이고, $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$ 입니다.
자주 묻는 질문
두 수가 모두 0이면 어떻게 되나요? 여기서는 0과 0의 GCD를 0으로 정의합니다. 양의 배수가 존재하지 않으므로 LCM도 0입니다.
약수를 일일이 나열하는 것보다 왜 빠른가요? 모든 약수를 찾는 대신 나머지를 이용한 지름길을 쓰기 때문입니다. 매 단계마다 문제 크기가 크게 줄어들어 보통 로그 시간(logarithmic time)에 해결됩니다.
아주 큰 수도 처리할 수 있나요? 가능합니다. 유클리드 호제법은 자릿수가 많은 수에도 효율적이며, 적은 횟수의 나머지 연산만으로 답을 구합니다.
