[수학] 최대공약수(GCD), 최소공배수(LCM) 알고리즘

🍀 목차
최대공약수, 최소공배수 알고리즘
기본 이해
구현(JavaScript)
시간 복잡도

최대공약수, 최소공배수 알고리즘

• 최대공약수(Greatest Common Divisor, GCD) : 두 수의 여러 공약수 중 최대인 수.
• 최소공배수(Least Common Multiple, LCM) : 두 수에 공통으로 존재하는 배수 중 가장 작은 수.
• A, B의 최대공약수를 구할 때 1부터 시작하여 Math.min(A, B)까지 A와 B가 나누어 떨어지는 최대의 수를 구하면 최대공약수를 구할 수 있지만 이 방법은 시간 복잡도가 O(n)이다.
• 그래서 최대공약수를 구할 때 유클리드 호제법을 쓴다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다. 나눠가며(log) 구해가기 때문에 훨씬 효율적이다. 

기본 이해

 A, B의 최대공약수는 B와 A%B의 최대공약수와 같다.

GCD(A, B) = GCD(B,A%B), A%B를 r이라 할 때, r이 0이면 B가 최대공약수가 된다. 그림으로 이해해보자.

 A가 15, B가 18이다. 최대공약수를 구해보자. 

 A,B의 최대공약수는 B, A%B의 최대공약수와 같다. (15와 18의 최대공약수는 18과 15의 최대공약수랑 당연히 같음. 더 큰 수를 A로 오게 하는 과정)

 그 전단계에서 B였던 15가 A가 되고, 18%15의 3이 B가 된다. 최대공약수가 N일 때, 3,15,18 모두 N의 배수이며 같은 최대공약수(N)를 가진다는 것을 알 수 있다.

 그 전단계에서 B였던 3이 A가 되고, 15%3의 0이 B가 된다. A%B가 0이 되었으니 B인 3이 최대공약수가 된다.

 

다음으로는 A = 1071, B = 1029일 때, A와 B의 최대공약수를 구해보자. 

1. A를 B로 모듈러 연산한다. (나머지를 구한다.)

1071을 1029로 나눈 나머지는 42이다.

 

2. 만약 나머지가 0이라면, B는 최대 공약수가 된다.

42가 나왔으므로 3번으로 넘어간다.

 

3. 만약 나머지가 0이 아니라면, A를 B로, B를 A%B로 바꿔 1번으로 돌아간다.

A를 1029, B를 42로 바꾼다.

 

1 👉 1029를 42로 나눈 나머지는 21이다. 

3 👉 A를 42, B를 21로 바꾼다.

1 👉 42를 21로 나눈 나머지는 0이다.

2 👉 B인 21이 1071, 1029의 최대공약수이다.

 

 최소공배수는 A가 15이고 B가 18일 때 90이 나오고,

A가 1071이고 B가 1029일 때 52479가 나온다.

이는 결국, 15(A)*18(B) = 3(GCD)*LCM -> LCM = 90

1071(A)*1029(B) = 21(GCD)*LCM -> LCM = 52479 이 된다.

 

따라서, A*B/GCD(A,B)가 최소공배수를 구하는 공식이다.

 

구현(JavaScript)

👉 재귀로 구현

const GCD = (a, b) => {
  if (b === 0) {
    return a;
  }
  return GCD(b, a % b);
};

👉 반복문으로 구현

const GCD = (a, b) => {
  while (true) {
    const r = a % b;
    if (r === 0) return b;

    a = b;
    b = r;
  }
};

---

const LCM = (a, b) => {
  return (a * b) / GCD(a, b);
};

시간 복잡도

$$O(logN)$$