알고리즘 - 유클리드 호제법

유클리드 호제법 (Euclidean-Algorithm)

---

유클리드 호제법이란 정수론에서 다루는 내용으로, 두 수의 최대 공약수(gcd)를 구하는 알고리즘입니다. 

 

일반적으로 최대 공약수를 구할 때 소인수분해를 이용할 수도 있지만, 유클리드 호제법을 이용하면 조금 더 간단하게 구할 수 있습니다.

 

일단 알려져 있는 공식은 다음과 같습니다.

 

두 양의 정수 a, b ( a > b )에 대하여 a = bq(몫) + r(나머지) ( 0 ≤ r < b )이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다.

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

r = 0이라면, a, b의 최대공약수는 b가 된다.

 

 

🔨 구현

---

mod(나머지, %) 연산을 이용해서 구현하며, 다음과 같은 과정으로 최대 공약수를 구할 수 있습니다.

1. 큰 수를 작은 수로 나누는 mod 연산을 수행
2. 작은 수와 mod 연산 결괏값(나머지)으로  mod 연산 수행
3. 나머지가 0이 되는 순간의 작은 수가 최대 공약수

 

보통 재귀함수로 많이 구현하며, 다음과 같이 구현할 수 있습니다.

public class Euclidean {
   
   // 재귀 함수 이용
   public static int gcd1(int a, int b) {
      return a % b == 0 ? b : gcd(b, a % b);
   }
   
   // while문 이용
   public static int gcd2(int a, int b) {
		while (a % b != 0) {
			int tmp = a;
			a = b;
			b = tmp % b;
		}

		return b;
	}
    
    // while문 이용 2
    public static int gcd3(int a, int b){
        while(b != 0){
        	int r = a % b;
            a = b;
            b = r;
        }
        
        return a;
    }

}

 

 

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

---

유클리드 호제법이 두 수의 최대 공약수를 구하는 것이라면, 확장 유클리드 호제법은 방정식의 해를 구하는 것입니다.

 

확장 유클리드 호제법은 베주 항등식의 명제를 가정으로 하여 방정식의 해를 구하기 때문에 우선 베주 항등식이 무엇인지 알아야 합니다.

 

 

 

📝 베주 항등식 (Bézout's Identity)

---

베주 항등식은 두 정수와 그 최대 공약수 사이의 관계를 보여주는 항등식입니다.

 

적어도 둘 중 하나는 0이 아닌 정수 a , b와 그 최대공약수 d가 존재할 때, 아래의 세 명제가 성립한다.

1. d = ax + by를 만족하는 정수 x , y 가 반드시 존재한다.
2. d는 정수 x, y에 대하여 ax + by로 표현할 수 있는 가장 작은 자연수이다.
3. 정수 x , y에 대하여 ax + by로 표현되는 모든 정수는 d의 배수이다.

 

베주 항등식을 통해 다음 방정식을 보면 다음과 같습니다.

ax + by = c 라는 식이 주어졌을 때, 베주 항등식에 의거하여 c는 gcd(a,b)의 배수이다.

즉,  c % gcd(a,b) = 0인 경우에만 정수해를 가진다.

 

이는 c의 최솟값이 gcd(a,b)이며 이를 통해 (x,y)를 구하는 것이 확장 유클리드 호제법입니다.

 

참고로 c % d != 0이라면 이를 만족하는 (x,y)의 값은 정수 범위에서 존재하지 않습니다.

 

 

🔨 구현

---

다음과 같은 방정식이 주어졌다고 가정하겠습니다.

5x + 9y = 2

 

베주 항등식에 의하여 5x + 9y가 정수해를 갖게 하는 c의 최솟값은 gcd(5,9) = 1이므로 다음과 식이 성립합니다.

5x + 9y = 1

이 식을 성립시키는 정수 (x, y)를 구하면 됩니다.

 

그 후, 유클리드 호제법을 이용하여 몫과 나머지를 저장합니다.

유클리드 호제법 이용

 

구해진 나머지와 몫을 이용하여 역순으로 다음 식을 계산합니다.

x_i = y_i-1   ,   y_i = x_i-1 - y_i-1 * q_i

 

기본적으로 b가 0이면 x = 1, y = 0으로 고정

 

• 1x + 0y = 1 -> x = 1 , y = 0

 

 

최종적으로  c / gcd(a,b) = K를 가정해보면, 최초 방정식의 해는 Kx, Ky이므로 답은 다음과 같습니다.

 

2 / 1 = 2 , x = 2 * 2 = 4 , y = 2 * -1  = -2

 

import java.util.Arrays;

public class ExtendedEuclidean {

   public static void main(String[] args) {

      int[] xy = findXY(5, 9, 2);

      System.out.println(Arrays.toString(xy)); // 4 , -2
   }

   public static int[] findXY(int a, int b, int c) {
      int d = getGCD(a, b);

      // c가 a,b의 최대 공약수의 배수인지 확인 (베주 항등식)
      if (c % d != 0) {
         return null;
      }

      int[] xy = recur(a, b);

      int K = c / d;

      return new int[]{K*xy[0] ,K*xy[1]};
   }

   private static int[] recur(int a, int b) {

      int[] xy = new int[2];

      // b 가 0이면 x,y는 기본적으로 1, 0
      if (b == 0) {
         xy[0] = 1;
         xy[1] = 0;
         return  xy;
      }

      // xi = yi-1   ,   yi = xi-1 - yi-1 * qi  계산
      int q = a / b;

      int[] prevXY = recur(b, a % b); // 이전 x,y 가져오기

      xy[0] = prevXY[1];
      xy[1] = prevXY[0] - prevXY[1] * q;

      return xy;
   }

   public static int getGCD(int a, int b) {
      while (b != 0) {
         int r = a % b;
         a = b;
         b = r;
      }
      return a;
   }

}