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

서론

현대 개발 환경에서는 수많은 문제를 해결하기 위해 다양한 알고리즘이 필요합니다. 그 중에서도 수학적 기법을 활용한 알고리즘, 특히 “확장 유클리드 호제법(Extended Euclidean Algorithm)”은 매우 유용한 도구입니다. 이 강좌에서는 확장 유클리드 호제법의 이론과 코딩테스트에서 자주 등장하는 문제를 통해 깊이 있게 다루어 보겠습니다. 이 내용을 통해 확장 유클리드 호제법을 체계적으로 이해하고 C++을 활용하여 실전 문제를 해결하는 능력을 기를 수 있게 될 것입니다.

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

유클리드 호제법은 두 정수 a, b의 최대공약수(GCD)를 구하는 알고리즘입니다. 확장 유클리드 호제법은 여기에서 나아가 a와 b의 GCD를 구하는 동시에, 그 GCD를 a와 b의 선형 조합으로 표현할 수 있는 정수 x, y를 찾는 방법입니다.

수학적으로, 이를 표현하면 다음과 같습니다:

gcd(a, b) = ax + by

여기서 x와 y는 정수이고, gcd(a, b)는 a와 b의 최대공약수를 나타냅니다.

확장 유클리드 호제법의 필요성

확장 유클리드 호제법은 주로 다음과 같은 문제를 해결하는 데 필요합니다:

모듈러 곱셈 역원 계산
선형 디오판 방정식 해결
암호 알고리즘 및 해시 알고리즘에서의 응용

문제 정의

이제 확장 유클리드 호제법을 활용한 알고리즘 문제를 정의해 보겠습니다. 문제는 다음과 같습니다:

주어진 두 정수 a와 b에 대해, 그들의 최대공약수와 함께 a와 b의 선형 조합으로 표현하는 정수 x와 y를 구하시오.

예를 들어, a = 30, b = 21일 경우, 최대공약수는 3이며, 이를 30과 21의 선형 조합으로 표현하면 다음과 같은 결과를 얻을 수 있습니다:

3 = 1 * 30 + (-1) * 21

문제 해결 과정

1. 알고리즘 설계

확장 유클리드 호제법의 기본 아이디어는 유클리드 호제법을 확장하여 최대공약수와 함께 필요한 x, y를 계산하는 것입니다. 아래와 같은 방식으로 알고리즘을 설계할 수 있습니다:

최대공약수와 더불어 x와 y값을 계산하기 위해 재귀적으로 함수를 호출합니다.
두 수 a와 b를 사용하여 다음과 같은 관계를 설정합니다:

gcd(a, b) = gcd(b, a % b)
기저 사례로는 b가 0일 때, gcd(a, 0) = a이며 x=1, y=0으로 설정합니다.
재귀 호출 후에는 x와 y를 업데이트하여 선형 조합을 구합니다.

2. C++ 구현

다음은 위의 알고리즘을 C++로 구현한 코드입니다:


#include <iostream>

using namespace std;

// 확장 유클리드 호제법
int extended_gcd(int a, int b, int &x, int &y) {
    // 기저 사례
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1; // 재귀 호출 후의 값
    int gcd = extended_gcd(b, a % b, x1, y1);
    
    // x와 y 업데이트
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd;
}

int main() {
    int a, b;
    int x, y;
    
    cout << "두 수를 입력하세요 (a b): ";
    cin >> a >> b;
    
    int gcd = extended_gcd(a, b, x, y);
    
    cout << "최대공약수: " << gcd << endl;
    cout << "x: " << x <<, " y: " << y << endl;
    
    return 0;
}

3. 코드 설명

위 코드는 주어진 두 수 a와 b에 대해 확장 유클리드 호제법을 구현하여 최대공약수와 x, y를 반환합니다.

extended_gcd 함수: 두 수와 x, y를 인자로 받아 최대공약수와 x, y 값을 계산합니다.
main 함수: 사용자로부터 두 수를 입력받아 extended_gcd 함수를 호출하고 결과를 출력합니다.

테스트 케이스

구현한 알고리즘을 테스트하기 위해 여러 가지 테스트 케이스를 사용해 보겠습니다. 예를 들어:

a	b	최대공약수 (GCD)	x	y
30	21	3	1	-1
48	18	6	1	-2
56	15	1	-2	7

결론

이번 강좌에서는 확장 유클리드 호제법의 이론과 C++을 활용한 문제 풀이 과정을 살펴보았습니다. 확장 유클리드 호제법은 최대공약수를 구하는 데 그치지 않고, 다양한 수학적 문제를 해결하는 데 널리 사용될 수 있습니다. 이러한 기본적인 이론을 바탕으로 더 복잡한 알고리즘 문제도 해결할 수 있는 능력을 기르시길 바랍니다.

서론