[코딩테스트] 확장 유클리드 호제법 접근 방법

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다. 

 

이 글은 증명보다는 방정식의 해를 구할 때 어떻게 접근해야 하는지 설명한다.

• 유클리드 호제법이 두 수의 최대공약수를 구하기 위한 것이라고 보면, 확장 유클리드 호제법은 방정식의 해를 구하는 것이라고 볼 수 있다. 
• 이름에서 알 수 있듯이 확장 유클리드 호제법은 기본 호제법을 알고 있어야 진행된다

ax + by = c

주어진 a, b, c, x, y는 모두 정수라고 생각한다. 이때 x, y의 해는 c % gcd(a,b) = 0 조건이 성립되어야 정수해를 구할 수 있다. 그렇기 때문에 문제에 접근할 때 먼저 c의 값이 gcd(a,b)의 배수가 맞는지 확인부터 해야 한다. 배수가 맞다면 일차 조건은 만족한 것이다.

 

c가 gcd(a,b)의 배수가 맞을 때는 다음과 같은 과정을 따른다.

•  ax + by = c에서 c의 최솟값이 gcd(a,b)인 것을 적용하여 ax + by = gcd(a,b)라고 식을 다시 세운다.
• 그런 다음 a, b에 대해서 나머지가 0이 될 때까지 유클리드 호제법을 적용한다. 이때 나머지와 몫을 계속 저장한다.
• 나머지가 0이 나와 반복을 중단하면 맨 마지막의 과정에서부터 거꾸로 x = y', y = x' - (y' * q)를 계산한다. (q는 몫)
• 처음의 x', y'는 각각 1, 0로 지정하여 계산한다. 이후의 계산된 x, y 값은 계속해서 다음 과정의 x', y'에 대입하여 최종적으로 x, y 값을 도출한다.
• 최종적으로 도출된 x, y는 ax + by = gcd(a,b)에 대한 해이기 때문에 c / gcd(a,b)를 각각 곱해야 최종해가 된다. 

백준의 확장 유클리드 문제를 통해 실제로 적용해 본다. (https://www.acmicpc.net/problem/21568)

https://www.acmicpc.net/problem/21568

 

왼쪽은 a, b, c를 나타내고 오른쪽은 그에 대한 x, y로 해를 나타낸다. 첫 번째와 두 번째, 세 번째는 사뭇 다른 출력 값이 나오는 것을 확인할 수 있다. 이것은 아까 말한 대로 c가 gcd(a,b)에 대한 배수가 되어야 한다는 조건 때문이다.

• 첫 번째 - gcd(1,2) = 1이므로 c인 3은 1의 배수로서 조건을 만족한다.
• 두 번째 - gcd(3,4) = 1이므로 c인 5는 1의 배수로서 조건을 만족한다.
• 세 번째 - gcd(6,8) = 2이기 때문에 c인 3은 2의 배수가 아니기 때문에 조건을 만족하지 않는다. 

이 중 두 번째 예시에 대한 접근 방법은 다음과 같다. 

3x + 4y = 5

• c인 5는 gcd(3,4) = 1에 대한 배수이기 때문에 3x + 4y = 1로 바꾼다. 
• 그 후 유클리드 호제법을 적용하여 몫과 나머지를 구하면 다음과 같다.

유클리드 호제법에서는 a < b일 때 자리를 바꾸어 큰 수가 앞으로 오도록 했지만, 확장 유클리드 호제법에서는 자리를 바꾸지 않는다. 왜냐하면 방정식에서는 x, y가 딱 구분되어 있기 때문에 바꾸게 되면 계수가 바뀌게 된다. 

유클리드 호제법 실행	나머지	몫
3 % 4 = 3	3	0
4 % 3 = 1	1	1
3 % 1 = 0	0	3

 

나머지가 0이 나왔기 때문에 호제법을 중단하고 x, y를 아래에서 위 방향으로 차례로 구한다. 세 번째 행부터 첫 번째 행 순서대로!

x = y', y = x' - (y' * q) (처음 계산하는 x', y'는 각각 1, 0)

유클리드 호제법 실행	x = y', y = x' - (y' * q) 계산
3 % 4 = 3	x = -1, y = 1 - ((-1) * 0) = 1
4 % 3 = 1	x = 1, y = 0 - (1 * 1) = -1
3 % 1 = 0	x = 0, y = 1 - (0 * 3) = 1

 

이로써 도출된 x, y의 해는 3x + 4y = 1(원래 식이 아님!) 방정식을 만족한다. 여기서 끝나는 게 아니라, x, y에 c / gcd(a,b)를 마저 곱해주어야 원하는 값을 얻을 수 있다. c = 5, gcd(a,b) = 1이었으니 5/1 = 5를 각각 곱해주어, x = -5, y = 5가 나오게 된다. 출력값을 확인해 보면 기대하는 결과가 잘 나온 것을 알 수 있다.

 

이제 코드로 바꾸어 보면 다음과 같다.

gcd 부분에 대해 좀 바꾸긴 했는데 예제 테스트에 대해서는 무리없이 돌아간다. 참고한 코드는 아래에! (저자 깃허브 21568 문제풀이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ21568 {
    /**
     * 확장 유클리드 호제법의 목적: 방정식의 해 구하기
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        long gcd = gcd(a, b);
        if (c % gcd != 0) {
            System.out.println(-1);
            return;
        }
        int num = (int)(c / gcd);
        long[] ret = extended_euclid(a, b);
        System.out.println(ret[0] * num + " " + ret[1] * num);
    }

    static long[] extended_euclid(int a, int b) {
        long[] ret = new long[2];
        if (b == 0) {
            ret[0] = 1;
            ret[1] = 0;              // y는 이미 0으로 초기화
            return ret;
        }
        long q = a / b;
        long[] v = extended_euclid(b, a % b);
        ret[0] = v[1];               // x = y'
        ret[1] = v[0] - (v[1] * q);  // y = x' - (y' * q)
        return ret;
    }

    static int gcd(int a, int b) {
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }
}

 

손으로 풀 때는 나머지와 몫을 먼저 계산한 뒤, x, y에 대해서 따로 계산했다. 코드에서는 어차피 재귀 함수를 호출하는 거니까 파라미터에 직접 지정만 해 주었고 반환되는 값에 대해서 차례로 x, y를 계산했다. 한꺼번에 연결하는 거다보니 반환 값에 대해 어떻게 처리가 되는지 헷갈렸는데 아래처럼 그림으로 이해해 보니까 흐름을 잡기 수월했다.