[Algorithm] 유클리드 호제법 (최대공약수 & 최소공배수 구하기)

유클리드 호제법

유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.

의무교육 과정에서 최대공약수를 구하는 방법을 두가지 배울텐데 소인수분해와 호제법을 배운다.

 

호제법을 쓰다보면 위 경우처럼 수가 크면 계산이 복잡해지고, 약수를 한번에 찾기가 힘든 경우가 있다.

이 때, 유클리드 호제법을 이용해서 쉽게 구할수 있다.

 

유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법이다. 하나만 기억해야하면

"A > B 일때, A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다."

1. 큰 수(A)를 작은 수(B)로 나눈다. ( A > B )
2. 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다.
3. 만약 나머지가 0이 아니라면, 작은 수(B)를 나머지(R)로 계속 나눈다.
4. 이를 반복해서 나머지가 0이 나오면, 나누는 수가 최대 공약수이다.

 

ex)

2304와 1440의 최대공약수

1. 2304(A) % 1440(B) = 1 ... 864(R)
2. 1440(B) % 864(1번의 R) = 1 ... 576(new R)
3. 864 % 576 = 1 ... 288
4. 576 % 288 = 2 ... 0 <-- 최대공약수는 288이다.

단계가 확 줄었다.

403과 155의 최대공약수

1. 403 % 155 = 2 ... 93
2. 155 % 93 = 1 ... 62
3. 93 % 62 = 1 ... 31
4. 62 % 31 = 2 ... 0 <-- 최대공약수는 31이다.

한번에 찾기 힘든 31을 쉽게 구할 수 있다.

 

프로세스

1. 큰 수를 작은 수로 나눈다. (num1이 num2보다 작을 경우, 1회 반복 후 스왑되기만 함)
   • 예를 들어 num1 = 14고, num2 = 77이라고 하면 gcd(14, 77) -> gcd(77, (14 % 77) === 14) -> gcd(14, 7) = gcd(7, 0)
2. 나누는 수를 나머지로 계속 나눈다. 
3. 나머지가 0이 나오면 나누는 수가 최대 공약수

 

최대공약수 (GCD. Great Common Divisor)

반복문

function gcd(a, b) { 
  while (b !== 0) { 
    const remainder = a % b; 
    [a, b] = [b, remainder]; // swap
  } 
  return a; 
}

재귀문

function gcd(a, b) { 
  return b ? gcd(b, a % b) : a; 
}

// Arrow function.
const gcd = (a, b) => b ? gcd(b, a % b) : a;

위 두 개의 방식에서는 두 수 중에서 큰 수를 작은 수로 나눈다고 했는데, 위의 코드에서는 그 과정이 빠져있다.

이는 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫이 0 이 되고 그 자신이 나머지가 되는 것을 응용한 것입니다.

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

 

최소공배수 (LCM. Least Common Multiple)

최소공배수(LCM)는 최대공약수(GCD)를 응용하면 구할 수 있다.

LCM = GCD * (num1 / GCD) * (num2 / GCD) 

즉, LCM = (num1 * num2) / GCD

두 수 의 곱은 최소공배수와 최대공약수의 곱과 같다는 원리를 이용한 것이다.

let lcm = a * b / gcd(a, b);