[Algorithm] 유클리드 호제법 알고리즘(Euclidean Algorithm) - 최대공약수(GCD), 최소공배수(LCM)

유클리드 호제법(Euclidean Algorithm)

유클리드 호제법 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나

2부터 1씩 늘려가며 두 자연수 중 작은 수까지 모두 나누어보는 방법은 시간복잡도가 O(N)인 반면

유클리드 호제법이란 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.

 

 

최대공약수(Greatest Common Divisor, GCD)

공약수(Common Divisor)란 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다.

최대공약수는 공약수 중 가장 큰 값을 의미한다.

 

 

최소공배수(Lowest Common Multiple, LCM)

공배수(Common Multiple)란 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다.

최소공배수는 공배수 중 가장 작은 값을 의미한다.

 

 

유클리드 호제법으로 최대공약수(GCD) 구하기

• a를 b로 나눈 나머지를 r이라고 할 때 (단, a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용
• 이를 반복하여 나머지가 0이 되었을 때 그 몫이 a와 b의 최대공약수다.

이를 수식으로 나타내면 아래와 같다.

GCD(A, B) = GCD(B, A%B)
if A%B = 0 -> GCD = B
else GCD(B, A%B)

 

 

최대공약수 코드 (C++)

// 반복문을 사용한 GCD
int gcd(int a, int b) {
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

// 재귀를 사용한 GCD
int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

// 숏코딩
int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

 

 

최소공배수 코드 (C++)

최소공배수 = 두 자연수의 곱 / 최대공약수 (LCM = A × B / GCD)

int lcm(int a, int b) {
  return a * b / gcd(a, b);
}