코틀린 코딩테스트 강좌, 확장 유클리드 호제법

코딩테스트에서 자주 등장하는 주제 중 하나가 바로 수학적 알고리즘입니다. 그중에서도 “확장 유클리드 호제법”은 두 수의 최대공약수(GCD)를 구하는 데에 그치지 않고, 더 나아가 Bézout의 항등식과 관련된 해를 제공하는 강력한 기법입니다. 이 글에서는 확장 유클리드 호제법을 설명하고, 이를 이용한 문제를 해결하는 과정을 상세히 설명드립니다.

확장 유클리드 호제법이란?

확장 유클리드 호제법은 두 정수 a와 b의 최대공약수 gcd(a, b)를 구하는 과정에서, 다음과 같은 정수 x와 y를 찾아내는 방법입니다:

gcd(a, b) = ax + by

위 식은 Bézout의 항등식이라고 불리며, x와 y는 정수입니다. 확장 유클리드 호제법은 재귀적 방법 또는 반복적인 방법으로 구현할 수 있습니다.

문제 정의

다음과 같이 숫자가 주어질 때, 확장 유클리드 호제법을 사용하여 최대공약수와 함께 Bézout의 계수를 출력하는 문제를 다룰 것입니다.

문제

문제 설명:

두 정수 A와 B가 주어질 때, 다음을 구하시오:

최대공약수 GCD(A, B)와

정수 X, Y를 찾아서 GCD(A, B) = AX + BY가 성립하도록 하라.

입력: 두 정수 A, B (-10⁹ ≤ A, B ≤ 10⁹)

출력: GCD(A, B), X, Y를 공백으로 구분하여 출력하시오.

문제 해결 과정

1. 기본 알고리즘 이해하기

우선, 확장 유클리드 호제법을 구현하기 위해서는 기본 유클리드 알고리즘을 이해해야 합니다. 유클리드 알고리즘은 두 수의 최대공약수를 구하는 유명한 방법으로, 다음과 같은 과정을 따릅니다:

두 수 A와 B가 0이 아닐 경우, A = A % B를 실행한다.
이 후 A와 B의 값을 바꿔 준다. A는 B로, B는 A (이전의 B)로 한다.
두 수 중 하나가 0이 될 때까지 반복한다.

최종적으로 남은 수가 최대공약수입니다. 이 과정에서 각 단계의 x와 y의 변화를 추적하여 Bézout의 항등식을 구성할 수 있습니다.

2. 확장 유클리드 알고리즘 구현하기

다음은 코틀린으로 확장 유클리드 호제법을 구현한 코드입니다:

fun extendedGCD(a: Int, b: Int): Triple {
    if (b == 0) {
        return Triple(a, 1, 0) // GCD = a, X = 1, Y = 0
    } else {
        val (gcd, x1, y1) = extendedGCD(b, a % b) // 재귀 호출
        val x = y1
        val y = x1 - (a / b) * y1
        return Triple(gcd, x, y) // 최대공약수, X, Y 반환
    }
}

위 함수는 입력으로 두 정수 a, b를 받아서, 최대공약수와 함께 Bézout의 계수인 x, y를 반환합니다.

3. 메인 함수 작성하기

이제 메인 함수에서 사용자로부터 두 수를 입력받고, 확장 유클리드 호제법을 호출하여 결과를 출력하는 코드를 작성해 보겠습니다:

fun main() {
    val reader = Scanner(System.`in`)
    println("두 정수를 입력하세요:")
    val A = reader.nextInt()
    val B = reader.nextInt()
    
    val (gcd, x, y) = extendedGCD(A, B)
    println("GCD: $gcd, X: $x, Y: $y")
}

4. 복잡도 분석

확장 유클리드 호제법의 시간 복잡도는 기본 유클리드 알고리즘과 동일합니다. 유클리드 알고리즘의 시간 복잡도는 O(log(min(A, B)))입니다. 이로 인해 확장 유클리드 호제법 또한 매우 효율적입니다.

5. 테스트 및 예제

이제 구현한 코드를 사용하여 몇 가지 테스트를 진행해 보겠습니다. 예를 들어, A = 30, B = 21일 때의 결과를 살펴보겠습니다:

두 정수를 입력하세요:
30
21
GCD: 3, X: -1, Y: 2

위의 결과는 3 = 30 * (-1) + 21 * 2로, Bézout의 항등식이 성립함을 보여줍니다.

결론

이번 포스팅에서는 확장 유클리드 호제법을 통해 두 수의 최대공약수와 Bézout의 항등식을 찾는 방법에 대해 알아보았습니다. 이 알고리즘은 다양한 문제 해결에 응용될 수 있으며, 특히 수학적 알고리즘과 관련한 문제에서 유용하게 활용될 수 있습니다. 복잡도 또한 낮아 실제 코딩 테스트에서도 높은 점수를 받을 수 있는 좋은 도구가 될 것입니다. 앞으로도 다양한 알고리즘과 문제 해결 방법을 함께 탐구해보길 바랍니다.