ABOUT ME

Today
Yesterday
Total
  • 유클리드 호제법(Euclidean algorithm)
    알고리즘 2024. 6. 9. 14:53

    사진출처: 위키피디아

     

    유클리드 호제법은 두 정수의 최대공약수(Greatest common divisor: GCD)를 구하는 효율적이고 간단한 알고리즘입니다. 기원전 300년경 그리스 수학자 유클리드(Euclid)가 편찬한 유클리드 원론(기하학 원론)에서 처음 소개돼었습니다. 가장 오래된 알고리즘으로 알려져 있습니다.

    두 정수 ab가 주어졌고 ab보다 크다고 하겠습니다. (a,bZa>b). ab로 나누면 a÷b=q이고 이는 a=bq+r 이렇게 다시 쓸 수 있습니다. 여기서 q는 몫(quotient)이고 r은 나머지(remainder)입니다. 여기서 ab의 최대공약수를 gcd(a,b)라고 표현하면 아래식이 성립합니다.

    gcd(a,b)=gcd(b,r)

    ab의 최대공약수는 br의 최대공약수와 같습니다. 여기서 다시 br로 나눈 나머지 r을 구하고 다시 rr로 나누는 과정 반복하다가 나머지가 0이 되었을 때 나누는 수가 최대공약수가 됩니다. 몇가지 예를 들어보겠습니다.

    gcd(4098,2024)=24098÷2024=250
    gcd(50,2024)=22024÷50=4024
    gcd(50,24)=250÷24=22
    gcd(2,24)=224÷2=120
    gcd(2,0)=2

    두 수 4098, 2024의 최대공약수는 2입니다.

     


    gcd(123456,9999)=gcd(3468,9999)=gcd(3468,3063)=gcd(405,3063)=gcd(405,228)=gcd(177,228)=gcd(177,51)=gcd(24,51)=gcd(24,3)=gcd(0,3)
    두 수 123456, 9999의 최대공약수는 2입니다.

     

     


    정리하자면 다음과 같습니다.  

    1. 두 정수 중 큰 수를 작은 수로 나눈 나머지로 바꿉니다. (만약 a>b라면 a=amodb)
    2. 두 정수 중 한쪽이 0이 될 때까지 반복합니다. 이때 0이 아닌 쪽이 최대공약수입니다.

    이에 대한 증명은 이 글에서 다루지 않습니다.

     

     

    다음은 위 내용을 C언어로 구현한 코드입니다. 유클리드 호제법의 시간 복잡도는 O(log(a+b))입니다.

    int gcd(int a, int b)
    {
    	while (a >= 1 && b >= 1)
    	{
    		if (a >= b)
    			a = a % b;
    		else
    			b = b % a;
    	}
    
    	if (a > 1)
    		return a;
    	return b;
    }
    
    int recur_gcd(int a, int b)
    {
    	if (b == 0)
    		return a;
    	else
    		return recur_gcd(b, a % b);
    }

    '알고리즘' 카테고리의 다른 글

    검사 범위 최소화하여 약수 구하기  (2) 2024.06.08
Designed by Tistory.