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

유클리드 호제법이란?

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를  활용한 알고리즘입니다.

ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8

 

 구현 (C / C++) 

재귀 함수 활용

int GCD(int a, int b)
{
    if(b==0)return a;
    else return GCD(b,a%b);
}

 

반복문 활용

int GCD(int a,int b){
    while(1){
        int r = a%b;
        if(r==0) return b;
		
        a = b;
        b = r;
    }
}

※ 단 a>b임을 가정

 

다항식일 경우

int a = 8;
int b = 16;
int c = 24;
	
int result = GCD(a,b); //a와 b의 최대공약수 -> result
result = GCD(result,c); //a와 b의 최대공약수 result와 c의 최대공약수

printf("%d",result);

다항식일 경우 GCD를 구하는 함수를 먼저 구현한 뒤 위와 같이 a와 b의 최대공약수를 먼저 계산한 후 계산된 최대공약수와 c의 최대공약수를 구하는 순차적인 방식으로 최대공약수를 구할 수 있습니다. 

 

장점

유클리드 호제법의 장점은 빠르다는 것입니다. 일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법이 있을 것 같은데 이의 경우 모든 정수를 나눠야 하므로 시간 복잡도는 O(N)이 됩니다. 하지만 유클리드 호제법을 사용한다면 비교대상의 두 수 a와 b에서 a를 b로 나눈 나머지를 r이라고 했을 때 a % r이 0이 될 때까지 반복을 해주는 방식으로 최대공약수를 산출하기에 시간 복잡도를 O(Log N)으로 줄일 수 있어 좀 더 효율적인 알고리즘을 작성할 수 있습니다.

 

단점

유클리드 호제법의 단점이라고 하면 최대공약수는 빠르게 산출이 가능하지만 최소공배수를 계산함에 있어서는 비교 대상의 초기값 a와 b를 특정 변수에 저장을 시키고 있어야 한다는 점입니다. 예를 들어 GCD(24,16) -> GCD(16,8) -> GCD(8,0)로 유클리드 알고리즘이 진행된다면 기존의 값 a와 b는 계속해서 그 숫자가 변할 것입니다. 이렇게 된다면 GCD * (GCD/a) * (GCD/b)인 최소공배수를 구할 수 없습니다. 

 

최소공배수 구하기

int LCM(int a, int b)
{
    return a * b / GCD(a,b);
}

GCD를 구하는 알고리즘을 먼저 유클리드 호제법을 활용하여 구현한 후 a * b / GCD(a, b)를 해주면 최소공배수를 구할 수 있습니다.