최대공약수(GCD), 최소공배수(LCM) - 유클리드 호제법

최대 공약수(GCD)와 최소 공배수를 구하는 유클리드 호제법에 대해서 알아보자

최소 공배수, 최대 공약수

보통 최대 공약수와 최소 공배수를 구할때는 위와 같은 방법으로 구한다. 

그래서 두 수의 공약수를 일일이 나열해서 찾는 방식으로 문제를 풀려고 했다. 그러려면 적어도 for문이 두 수 중에서 제일 큰 수까지 돌면서 같은 공약수가 있는지를 체크해야 한다. 그러면 O(N)의 시간복잡도를 가지게 된다. 

 

하지만, 유클리드 호제법을 사용하면 시간복잡도를 O(log N)으로 줄일 수 있다. 이 방법에 대해서 알아보자. 

 

 

1. GCD (최대공약수)의 핵심 원리 - 유클리드 호제법

두 수 a, b(a>b)가 있을 때, a를 b로 나눈 나머지를 r이라고 하면, GCD(a,b) = GCD(b,r)이 성립한다. 

2. LCM (최소공배수)와의 관계

⭐️ 두 자연수 A, B가 있을 때, 두 수를 곱한 값은 최대공약수와 최소공배수를 곱한 값과 같습니다. ⭐️

A X B = GCD(A,B) X LCM(A,B)

이 식을 LCM 기준으로 바꾸면 다음과 같습니다. 

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

3. 구현방법

재귀(Recursive)방식과 반복문(Iterative)방식 2가지 모두 가능합니다. 

// 1. 재귀 방식 (가장 깔끔함)
const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));

// 2. 반복문 방식 (스택 오버플로우 걱정 없음)
function getGCD(a: number, b: number): number {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

// 3. 최소공배수
const getLCM = (a: number, b: number): number => (a * b) / gcd(a, b);

Tip) 최소공배수를 구할때, a*b를 먼저 계산하면 오버플로우 위험이 있어서, 나누기를 먼저한 후에 곱하면 조금 더 안전한 방법으로 값을 구할 수 있습니다. 

 

 

출처(이미지)

https://velog.io/@h_zee/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95