유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법 (Euclidean Algorithm)

2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘

 

일반적으로 최대 공약수를 가장 구하기 쉬운 방법은 2 부터 min (a, b) 까지 모든 정수를 나누어 구하는 O(n) 방법이있지만 유클리드 호제법을 사용한다면 시간 복잡도를 O(log n)으로 줄일 수 있어 좀 더 효율적인 알고리즘이다.

 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b)

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고,

다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대공약수이다.

 

 

예를들어 78696 과 19332의 최대공약수는

 78696 ＝ 19332×4 + 1368
 19332 ＝ 1368×14 + 180
  1368 ＝ 180×7 + 108
   180 ＝ 108×1 + 72
   108 ＝ 72×1 + 36
    72 ＝ 36×2 + 0

나머지가 0이 되었을때 나누는 수가 최대공약수 (32) 이다.

 

 

이를 코드로 구현하면 다음과 같다.

int GCD(int a, int b)
{
    if (a < b)  // b가 a보다 크면 a 와 b 값을 바꾼다.
    {
        int tmp = a;
        a = b;
        b = tmp;
    }

    while(b != 0) // b 가 0 이 되었을 때 나누는 수가 a 와 b 의 최대공약수 이다. 
    {
        int n = a % b;
        a = b;
        b = n;
    }

    return a;
}

int LCM(int a, int b)  // 두 수의 최소공배수는 두 수의 곱 / 최대공약수
{
    return a * b / GCD(a , b);
}

 

 

확장된 유클리드 호제법 (Extended Euclidean Algorithm)

ax + by = c에서 c의 값이 gcd(a, b)의 배수일 때만 정수해를 갖는다고 알려져있다.

따라서 ax + by = c가 정수해를 갖는 c의 최솟값이 gcd(a,b)가 되는 것이다.

이를통해 확장 유클리드 알고리즘은 a, b의 최대 공약수와 ax + by = gcd(a,b)를 만족하는 x, y도 구하는 알고리즘

 

 

두 정수 a, b 에 대해 유클리드 호제법을 이용하면 다음과 같이 나열된다.

void EEA(int a, int b)
{
    int q, r0, r1, r, s0, s1, s, t0, t1, t;

    r0 = a , r1 = b;
    s0 = 1 , s1 = 0 , t0 = 0, t1 = 1;


    while(r1 != 0)
    {
    	
    	q = r0 / r1;
	r = r0 - (r1 * q);
        s = s0 - (s1 * q);
        t = t0 - (t1 * q);

        r0 = r1;
        r1 = r;
        
        s0 = s1;
        s1 = s;
        
        t0 = t1;
        t1 = t;
    }

    cout << "d: " << r0 << endl;
    cout << "x: " << s0 << endl;
    cout << "y: " << t0 << endl;
}