수학에서 유클리드 알고리즘(유클리드 호제법)은 두 수의 최대공약수(GCD, Greatest Common Divisor), 즉 두 수를 모두 나머지 없이 나누어떨어지게 하는 가장 큰 수를 구하는 고전적인 방법입니다.
유클리드 호제법의 원리
이 알고리즘은 다음과 같은 원리에 기반합니다. 두 수의 최대공약수는 더 큰 수를 '큰 수에서 작은 수를 뺀 차이'로 바꾸더라도 변하지 않는다.
예를 들어 252와 105의 최대공약수는 21입니다(252 = 21 × 12, 105 = 21 × 5). 동시에 21은 105와 252 − 105 = 147의 최대공약수이기도 합니다.
이 치환 과정은 두 수 중 더 큰 값을 줄여주기 때문에, 과정을 반복할수록 숫자 쌍은 점점 작아지고 결국 두 수가 같아지는 지점에 도달합니다. 그때의 값이 바로 원래 두 수의 최대공약수입니다.
또한 단계를 거꾸로 거슬러 올라가면, 최대공약수는 원래 두 수에 각각 정수를 곱한 값의 합 형태로도 표현할 수 있습니다. 예를 들면 다음과 같습니다.
21 = 5 × 105 + (−2) × 252
JavaScript 구현
두 개의 숫자를 입력받아 유클리드 알고리즘을 활용해 최대공약수를 계산하는 JavaScript 함수를 작성해 보겠습니다.
코드
const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
let a = Math.abs(num1);
let b = Math.abs(num2);
while (a && b && a !== b) {
if(a > b){
[a, b] = [a - b, b];
}else{
[a, b] = [a, b - a];
};
};
return a || b;
};
console.log(findGCD(num1, num2));출력 결과
콘솔 실행 결과는 다음과 같습니다.
21
코드 설명
- Math.abs(): 음수가 입력되더라도 올바른 최대공약수를 구할 수 있도록 두 수를 절댓값으로 변환합니다.
- while 루프: 두 수가 모두 0이 아니고 서로 다를 때까지 반복하며, 매번 더 큰 수에서 작은 수를 빼는 연산을 수행합니다.
- 구조 분해 할당([a, b] = ...): 임시 변수 없이 간결하게 두 변수의 값을 교체합니다.
- return a || b: 두 수가 같아져 루프가 종료된 경우 해당 값을 반환하고, 한쪽이 0이 된 경우 나머지 값(최대공약수)을 반환합니다.
이처럼 유클리드 호제법은 뺄셈만으로도 최대공약수를 구할 수 있는 간단하면서도 강력한 알고리즘입니다. 실무에서는 뺄셈 대신 모듈로 연산(%)을 사용하면 반복 횟수를 크게 줄여 더 빠르게 계산할 수 있습니다.