JavaScript로 배우는 유클리드 호제법 (GCD with Euclidean Algorithm)

유클리드 호제법이란?

"유클리드 호제법(Euclidean Algorithm)"은 두 자연수의 "최대공약수(Greatest Common Divisor, GCD)"를 효율적으로 구하는 고전적인 수학 알고리즘입니다. 이 방식은 기원전 유클리드가 『기하학 원론』에서 소개한 방법으로, 간단하면서도 강력한 계산 원리를 기반으로 합니다. 알고리즘 문제 풀이뿐만 아니라 실제 시스템 설계나 암호 알고리즘에서도 활용되는 등, 실무와 이론 양쪽에서 중요한 위치를 차지하고 있습니다.

핵심 아이디어는 다음과 같습니다:

• 두 수 A, B가 있을 때 (단, A > B), A를 B로 나눈 나머지를 R이라고 하면,
• A와 B의 최대공약수는 곧 B와 R의 최대공약수와 동일합니다.
• 이 과정을 B가 0이 될 때까지 반복하면, 마지막에 남는 수가 GCD입니다.

이 알고리즘은 재귀 호출이나 반복문을 통해 간결하게 구현할 수 있으며, 계산량이 작고 안정적입니다.

 

---

재귀 방식으로 구현하기

아래는 JavaScript로 구현한 재귀 방식의 유클리드 알고리즘입니다:

// 두 수의 최대공약수를 구하는 재귀 함수
function gcdRecursive(a, b) {
  // b가 0이 되면 a가 GCD
  if (b === 0) return a;
  // 재귀적으로 호출 (b와 a % b)
  return gcdRecursive(b, a % b);
}

// 예제 실행
console.log(gcdRecursive(48, 18)); // 출력: 6

이 방식은 문제를 반복적으로 더 작은 문제로 쪼개서 해결하는 "재귀 함수"의 특징을 잘 보여줍니다. 특히 이 구현은 코드가 간결하고 직관적이기 때문에 알고리즘의 흐름을 이해하는 데 효과적입니다.

 

---

반복문으로 구현하기 (while loop)

재귀와는 달리 반복문을 이용하면 호출 스택을 사용하지 않으므로 메모리 효율이 더 좋습니다. 다음은 while 반복문을 활용한 방식입니다:

// 두 수의 최대공약수를 구하는 반복문 함수
function gcdIterative(a, b) {
  while (b !== 0) {
    const temp = b;      // 현재 b를 임시 저장
    b = a % b;           // b는 a % b로 갱신
    a = temp;            // a는 이전 b로 갱신
  }
  return a; // b가 0이 된 순간의 a가 GCD
}

// 예제 실행
console.log(gcdIterative(48, 18)); // 출력: 6

실제 프로덕션 환경에서는 반복문 방식이 더 선호되는 경우가 많습니다. 특히 재귀 깊이가 깊어질 수 있는 상황에서는 반복문이 안정적입니다.

 

---

최소공배수(LCM) 계산까지 확장하기

"최소공배수(Least Common Multiple, LCM)"는 두 수가 공통으로 가지는 배수 중 가장 작은 수입니다. LCM은 GCD를 이용하여 다음과 같은 공식으로 효율적으로 구할 수 있습니다:

LCM(A, B) = (A * B) / GCD(A, B)

이를 기반으로 JavaScript 함수는 다음과 같이 작성할 수 있습니다:

// 최소공배수를 구하는 함수 (GCD를 활용)
function lcm(a, b) {
  return (a * b) / gcdIterative(a, b);
}

// 예제 실행
console.log(lcm(12, 18)); // 출력: 36

LCM 계산은 분수의 통분이나 다항식의 최소 단위 설정 등 수학 문제에서 자주 활용됩니다.

 

---

시간 복잡도 및 활용 분야

• 유클리드 알고리즘은 수학적으로 O(log N)의 시간 복잡도를 가집니다. 이는 매우 효율적인 성능으로, 큰 수에 대해서도 빠르게 계산이 가능합니다.
• 메모리 공간도 O(1) 수준으로 효율적입니다.

실제 활용 분야는 다음과 같습니다:

• 분수의 통분 계산
• 암호학 알고리즘 (예: RSA에서의 모듈러 연산)
• 컴퓨터 시스템 설계에서 스케줄링 주기 계산
• 수학 문제 풀이 및 교육용 알고리즘

---

마무리 및 CTA

유클리드 호제법은 알고리즘의 기본적인 사고를 다지는 데 매우 적합한 주제입니다. 특히 "재귀 함수"와 "반복문"을 비교하며 학습하면, 코드 구현에 대한 깊은 이해를 얻을 수 있습니다. 또한, GCD를 확장하여 LCM까지 활용할 수 있는 점은 실용적인 가치가 높습니다.

이 알고리즘에 대한 이해를 더욱 깊이 있게 확장하고 싶다면 다음 자료를 참고해보세요:

추천 자료:

• GeeksforGeeks - Euclidean Algorithm
• Brilliant - Recursive Thinking