[Javascript] 최대공약수 알고리즘 (with 유클리드 알고리즘)

intro

최대공약수 알고리즘은 중학생(?) 정도의 수학을 요구하는 아주 간단한 알고리즘입니다. 그 자체로도 난이도가 어려운 편은 아니지만, 오늘은 유클리드 알고리즘(a.k.a. 유클리드 호제법)이라는 공식을 활용해 간단하면서도 선언적인 최대공약수 알고리즘을 "자바스크립트"로 작성해 보겠습니다.

유클리드 알고리즘(유클리드 호제법)

유클리드 알고리즘은 두 자연수 사이의 최대공약수를 구하는 알고리즘으로, 명시적으로 기술된 가장 오래된 알고리즘으로 알려져 있다고 합니다.

원리를 풀면 의외로 간단합니다.

1. 두 수 중에서 큰 수를 작은 수로 나눈다.
2. 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다.
3. 만약 나머지가 0 이 아니라면, 작은 수를 다시 나머지로 나눈다.
4. 이를 반복해서 나머지가 0 이 될 때, 그 수가 바로 두 수의 최대공약수이다.

with Javascript

위키백과에서 이미 다양한 언어로 구성된 알고리즘을 소개하고 있습니다만, 꼭 자바스크립트는 없는 경우가 많더라구요. 어차피 원리는 유클리드 알고리즘에서 가져올 예정이니 코드로 어떻게 작성하면 될지만 얼른 살펴보겠습니다.

function gcd(a, b) {
  const remainder = a % b;  // 1번
  if (remainder === 0) return b;  // 2번
  return gcd(b, remainder);  // 3번
}

두 수 중에서 큰 수를 작은 수로 나눈다고 했는데, 위의 코드에서는 그 과정이 빠져있습니다. 이는 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫이 0 이 되고 그 자신이 나머지가 되는 것을 응용한 것입니다.

만약 a 가 작은 수이고 b 가 큰 수라고 한다면, remainder 의 값은 a 가 될 것입니다. 그렇게 되면 3번에서 둘의 위치를 바꾼채로 함수가 재귀적으로 돌아가기 때문에 굳이 큰 수를 작은 수로 분기해주는 과정이 필요하지 않은 것이죠.

이렇게 단 3 줄로 알고리즘이 완성되었습니다. 물론 간결한 코드가 그 자체로 선언적인 코드가 되는 것은 아닙니다만, 최소한 유클리드 알고리즘을 이해하는 사람에게는 선언적인 코드가 될 수 있지 않을까 합니다.