[Javascript] 최대공약수(GCD) 구하기

프로그래머스 - 분수의 덧셈을 풀다가 최대공약수(GCD) 계산이 필요했다. 유클리드 호제법을 이용해 최대공약수를 구해보자

유클리드 호제법

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

상대방의 수를 나누어 원하는 수를 얻는 알고리즘으로 2개의 자연수 a, b에 대해서 (단 a > b일 경우) a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. r이 0이라면, b가 a와 b의 최대공약수가 된다.

구현

재귀 함수를 이용해 유클리드 호제법을 구현하였다.

const getGCD = (num1, num2) => {
  if (num2 === 0) return num1
  
  return getGCD(num2, num1 % num2)
}

만약 num2가 num1보다 큰 수를 넣더라도 처리가 된다. num2가 30, num1이 10이라 할때,
getGCD(10, 30) = getGCD(30, (10 % 30 = 10)) = getGCD(10, 0) = 10

삼항 연산자를 이용하면 한줄로 작성이 가능하다.

const getGCD = (num1, num2) => num2 === 0 ? num1 : getGCD(num2, num1 % num2)