[Algorithm] 최대공약수 구하기 (유클리드 알고리즘)

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

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법
유클리드의 원론에 적혀있는 내용으로 인류 최초의 알고리즘이라고 함 !
( 호제법이란 ? 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘 )

최대공약수란?

공통된 약수중 가장 큰 값을 의미한다.
[ 12와 18의 최대 공약수 구하기 ]

12의 약수는 { 1, 2, 3, 4, 6, 12 }
18의 약수는 { 1, 2, 3, 6, 9, 18 }
공약수는 { 1, 2, 3, 6 } 이고
공약수중 최댓값은 6 이다. (최소공약수는 무조건 1이라 의미없다.)

따라서, 최대공약수는 6이다.

How to

1. 두 수 중에 큰 수를 작은수로 나눈다.
2. 나머지 값을 확인한다.
   2-1. 나머지 값이 0이라면, 작은 수가 최대 공약수 이다.
   2-2. 나머지 값이 0이 아니라면, 작은 수를 나머지 값으로 나눈다.
3. 위를 반복해서 나머지 값이 0이 되면, 그 수가 바로 두 수의 최대공약수이다.

예시

1071과 1029의 최대공약수를 구하면,

1071 = (1029 * 1) + 42
// 1071은 1029로 나누어 떨어지지 않기 때문에 1071를 1029로 나눈 나머지를 구한다. >> 42

1029 = (42 * 24) + 21
// 1029는 42로 나누어 떨어지지 않기 때문에 1029를 42로 나눈 나머지를 구한다 >> 21

42 = (21 * 2)
// 42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

JavaScript 소스코드

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

a, b의 크기 비교 과정은 제외 !

why ?
어떤 수를 자신보다 큰 수로 나누게 되면 몫이 0, 나머지 값은 본인이 된다.
그렇게 되면 3번째 줄에서 a, b 둘의 위치를 바꾼채 함수가 재귀적으로 돌아가기 때문에
굳이 큰 수를 작은 수로 분기해 크기를 비교하는 과정이 필요하지 않다.

참고 사이트
위키백과 - 유클리드 호제법
https://velog.io/@eensungkim/Javascript-최대공약수-알고리즘-with-유클리드-알고리즘