[Algorithm] 유클리드 호제법 (GCD 알고리즘)

유클리드 호제법은 두 정수의 최대공약수(GCD)를 구하는 알고리즘으로, 한 수를 다른 수로 나누어 나머지가 0이 될 때까지 반복한다.

---

1. GCD(최대공약수)란?

GCD(Greatest Common Divisor)는 두 개 이상의 자연수에 공통으로 존재하는 약수 중 가장 큰 수를 의미한다. 예를 들어, 12와 18의 공약수는 1, 2, 3, 6이며, 이 중 가장 큰 수인 6이 최대공약수(GCD)다.

2. 유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 수의 최대공약수를 구하는 가장 효율적인 알고리즘이다. 이 방법은 다음 원리를 이용한다.

“두 자연수 a와 b (단, a > b)에 대해, a를 b로 나눈 나머지를 r이라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.”

이 과정을 나머지가 0이 될 때까지 반복하면, 그 직전의 나머지가 바로 두 수의 최대공약수가 된다.

3. 알고리즘 과정

두 수 1071과 1029의 최대공약수를 유클리드 호제법으로 구한다.

1. 1071을 1029로 나눈 나머지: $1071 = 1029 \times 1 + 42$ 이제 1029와 42의 최대공약수를 구한다.

2. 1029를 42로 나눈 나머지: $1029 = 42 \times 24 + 21$ 이제 42와 21의 최대공약수를 구한다.

3. 42를 21로 나눈 나머지: $42 = 21 \times 2 + 0$ 나머지가 0이 되었다.
   

따라서 이 과정의 직전 나머지인 21이 1071과 1029의 최대공약수가 된다.

4. C# 코드 구현

재귀 함수 또는 반복문을 사용하여 유클리드 호제법을 구현할 수 있다.

public class GCDAlgorithm
{
    // 재귀 함수를 이용한 GCD
    public int GCD(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
        return GCD(b, a % b);
    }
}

public class GCDAlgorithm
{
    // 반복문을 이용한 GCD
    public int GCD(int a, int b)
    {
        while (b != 0)
        {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}