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

안녕하세요, 오늘은 코딩테스트에서 자주 등장하는 알고리즘 중 하나인 확장 유클리드 호제법에 대해 알아보겠습니다. 이 글에서는 확장 유클리드 호제법의 기본 원리, 이를 활용한 문제를 살펴보고, C#을 사용하여 문제를 해결하는 방법을 다룰 것입니다.

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

확장 유클리드 호제법(Extended Euclidean Algorithm)은 두 정수 a와 b에 대해 다음 두 가지를 찾는 알고리즘입니다:

두 수 a와 b의 최대공약수( gcd(a, b) )를 구합니다.
그 최대공약수를 a와 b의 비율에 해당하는 정수 x, y를 찾아서 표현할 수 있도록 합니다. 즉, gcd(a, b) = ax + by의 형태로 나타낼 수 있습니다.

이 알고리즘은 주로 모듈러 항등식이나 선형 방정식의 해를 구하는 데 사용됩니다. 특히, 암호학에서 중요한 역할을 합니다.

2. 알고리즘의 필요성

유클리드 호제법의 확장형은 Euclidean algorithm의 변형이며, 나머지 계산을 통해 두 수의 최대공약수를 구할 수 있습니다. 하지만 단순히 최대공약수를 찾는 것에 그치지 않고, 추가적으로 두 수를 조합하여 그 최대공약수를 도출할 수 있다는 점에서 그 유용성이 빛납니다. 이 과정을 통해 얻는 x와 y는 특정한 문제에서 매우 유용한 도구가 될 수 있습니다.

3. 알고리즘의 구현

먼저, 확장 유클리드 호제법을 구현하기 위한 기본적인 C# 함수를 정의해 보겠습니다. 이 함수는 두 개의 정수 a와 b를 인자로 받아, 해당하는 최대공약수와 함께 x와 y의 값을 반환합니다.


using System;

class Program
{
    static void Main(string[] args)
    {
        int a = 252;
        int b = 105;
        
        var result = ExtendedGCD(a, b);
        Console.WriteLine($"gcd: {result.Item1}, x: {result.Item2}, y: {result.Item3}");
    }

    static (int, int, int) ExtendedGCD(int a, int b)
    {
        if (b == 0)
        {
            return (a, 1, 0);
        }

        var (gcd, x1, y1) = ExtendedGCD(b, a % b);
        
        int x = y1;
        int y = x1 - (a / b) * y1;

        return (gcd, x, y);
    }
}

3.1 코드 설명

이 코드의 주요 부분은 ExtendedGCD라는 함수를 구현하는 것입니다. 이 함수는 재귀적으로 호출되어 두 수의 최대공약수를 찾습니다:

기저 사례로, b가 0일 경우, gcd는 a이며, x는 1, y는 0을 반환합니다.
그렇지 않은 경우, a와 b를 활용하여 재귀적으로 호출하고, 반환된 값을 사용하여 새로운 x와 y를 계산합니다.

4. 예제 문제: 최대공약수와 계수 구하기

이제 확장 유클리드 호제법을 활용하여 구체적인 문제를 해결해 보겠습니다. 예를 들어, 두 정수 a = 252와 b = 105를 가지고 그들의 최대공약수와 계수 x, y를 구하겠습니다.

4.1 문제 정의

주어진 두 수 a와 b에 대해, 다음을 구하시오:

gcd(a, b)
x, y를 찾아 gcd(a, b) = ax + by를 만족시키는 x와 y의 값을 구하시오.

4.2 풀이 과정

주어진 문제에서 a = 252, b = 105를 대입하여, 확장 유클리드 호제법을 적용한다. 아래는 그 과정입니다:

ExtendedGCD(252, 105) 호출
여기서 b = 105, 재귀적으로 ExtendedGCD(105, 252 % 105)로 호출
계속해서 252 % 105 = 42로 변환된 ExtendedGCD(105, 42)로 접근
이제 ExtendedGCD(42, 21) 호출
마지막으로 ExtendedGCD(21, 0)에 도달하게 되면, 최대공약수인 21을 반환하며 x=1, y=0 조합이 함께 전달됩니다.

재귀의 반환 과정에서 x와 y의 값을 하나씩 업데이트하며, 최종적으로 gcd(252, 105) = 21과 함께 x와 y의 값을 찾을 수 있습니다. 이 값들을 활용하여 주어진 수의 선형 조합으로 최대공약수를 표현합니다.

4.3 결과

이 과정을 통해 얻은 결과는 다음과 같습니다:

gcd(252, 105) = 21
x = -1, y = 3으로, 즉 21 = 252 * (-1) + 105 * 3의 형태로 표현될 수 있습니다.

5. 실습문제

여기까지 확장 유클리드 호제법을 이해하고 구현하는 과정을 살펴보았습니다. 다음 연습 문제를 통해 여러분도 직접 확장 유클리드 호제법을 구현해 보세요.

연습 문제

다음의 두 정수에 대해 확장 유클리드 호제법을 이용하여 최대공약수와 그 계수 x, y를 구해보세요:

a = 119, b = 544

여러분의 답안을 작성하고, 구현한 C# 코드를 통해 확인해 보세요!

6. 결론

오늘은 확장 유클리드 호제법에 대해 알아보았습니다. 이 알고리즘은 하나 이상의 수의 최대공약수를 찾는 데 매우 유용하고, 그 결과를 선형 조합으로 나타낼 수 있어 다양한 수학적 문제를 푸는 데에 활용될 수 있습니다. 이러한 지식은 코딩테스트뿐만 아니라 실제 프로그래밍에서도 매우 중요합니다. 다음 고급 주제로 넘어가기 전에 한 번 더 이 알고리즘을 복습하고, 다양한 문제를 통해 연습해보시길 권장합니다.