유클리드 호제법(Euclidean algorithm)

이론

1. 유클리드 호제법이란?

두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다. 원리는 두 수가 서로 나눠서 나머지를 구한다. 만약 나머지가 0이면 그 수가 최대 공약수가 되는것이다. 만약에 나머지가 0이 아니면 나머지가 0일 될때까지 두 수를 나누어 주면 된다. 기존 최대공약수를 구할때는 2개 이상에 각 수의 약수를 구한다음 공통으로 있는 약수중 최대값을 구해야 했다. 

위의 그림을 보면 30, 24에서 학교에서 기본것으로 배운 토대로 최대공약수를 구한다면 먼저, 약수를 구해서 공통된 수가 6, 3, 2, 1이고 이중에서 가장 큰것이 6이다. 6이라는 숫자가 30, 24 최대 공약수이다 수가 30, 24라서 각 약수의 수가 적어서 구하는데 금방 걸리는데 100단위 또는 1000단위 이상 그리고 수가 여러개일 경우 일일이 약수 구하는게 시간이 많이 걸릴것이고 공톤된 숫자 찾는 시간이 많이 소모가 된다. 그래서 유클리드 호제법을 사용하면 최대공약수, 최소 공배수를 빨리 구할수 있을것이다.

 

2. 유클리드 호제법 최소공약수 구하는 방법

a, b 두 수가 있다면 a, b를 나누어서 나머지를 r이라고 하면, r이 0이면 b가 최대 공약수 이다. 만약 아닌경우 a'는 b이고 b'는 r 이라고 할때 a', b'를 나누어서 나머지를 r'이라고 하면 r'가 0이 될때까지 위에 방법대로 진행 하면 된다.

※ 예시

 30, 24 두 수에서 유클리드 호제법으로 구한다면...

1. 30 % 24 = 6
2. 24 % 6 = 0 

6이 최대공약수가 된다. 반대로 한 번 구해 보겠다.

1. 24 % 30 = 24
2. 30 % 24 = 6
3. 24 % 6 = 0

두 수를 바꿔서 해도 결과가 6인것은 똑같지만 연산을 1번 더 해야되서 앞의 수는 나눠야 할 수보다 큰게 좋다.

 

이번에는 150, 108 최대공약수를 구해 보겠다.

1. 150 % 108 = 42
2. 108 % 42 = 24
3. 42 % 24 = 18
4. 24 % 18 = 6
5. 18 % 6 =0

위 결과 대로 6이 최대 공약수가 된다. 만약 150, 108 약수를 다 구하는 방식으로 했으면 약수가 10개 이상 나올수가 있고 실수할 가능성이 크다.  하지만 유클리드 호제법을 사용하면 약수 구하는 시간이 많이 절약되고 실수도 거의 없을것이다.

 

3. 유클리드 호제법 최소공배수 구하는 방법

최대공배수는 최대공약수만 구하면 끝이다. 두 수 a, b가 있다면  a, b를 곱해서 최대공약수를 나누면 된다.

최대 공약수

30, 24  최소공배수를 구한다면 최대 공약수는 6이다. 그 다음 30 을 24 곱해서 6을 나누면 120이 나온다. 그럼 120이라는 수가 최대공약수가 된다.

학교에서 배운 방식대로 최소공배수를 구한다면 각 수를 소수에서 지수를 만든다면 두 수 공통된것있으면 그 중 지수가 가장 높은값으로 해서 구해야 한다. 하지만 유클리드 호제법을 사용 하면 최대 공약수만 구하고 곱해서 나누면 끝이다.

 

4. 시간 복잡도

function GCD(a, b) {
  let result;
  
  // a 가 b보다 작으면 위치 변경
  if( a < b ){
  	let tmp = a;
    b = a;
    a = tmp;
  }
  
  for(i = b - 1; i > 1; i--){
  	if(a % i == 0 && b % i ==0){
    	result = i;
        break;
    }
  }
  return result;
}

 위에 코드를 보면 한개씩 찾는 경우 시간 복잡도는 O(N)이다. 하지만 유클리드 호제법을 사용할 경우 O(logN)의 시간 복잡도가 나온다. 그 이유는 각 수의 나머지를 구하는 방식이라서  x % y 에서 y보다  작은 수가 나오기 때문이고  나머기가 r이라고하면 r이 0이 될때까지 돌아가기 때문에 r 값이 한개또는 n개씩 줄어들지 않아서 O(logN)시간이 걸린다.

코드

이제 이론은 봤으면 코드로 구현해볼 차례이다. 알고리즘 순서는 이렇다.

1. 입력값 두 수 x, y를 받아온다. 단 x가 y보다 커야 된다.
2. x가 y를 나누어 떨어지면 y를 가 최대 공약수가 된다.
3. x가 y를 나누어 떨어지지 않을때는 나머지  r을  y에 대입하고  y는 x에 대입한다.
4. x가 y가 나누어 떨어질때까지 3번 방법으로 계속한다.
5. 최대 공약수는 x, y를 곱해서 최대공약수를 나누면 된다.

Python

def GCD(x, y):
    while(x % y != 0 and x != 0):
        r = x % y
        x, y = y, r
    return y

def LCM(x, y):
    return x * y // GCD(x, y)

※ 파이썬에서는 math 패키지에 gcd 함수를 제공한다.

JAVA

public static int GCD(int x, int y) {
    int r;
    while(x % y != 0) {
        r = x  % y;
        x = y;
        y = r;
    }
    return y;
}

public static int LCM(int x, int y) {
    return x * y / GCD(x, y);
}