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

서론

코딩 테스트에서 자주 출제되는 알고리즘 중 하나인 유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 효율적으로 구하는 방법입니다.
이 방법은 고대 그리스 수학자 유클리드가 소개했으며, 알고리즘의 기초에 해당하는 내용이기 때문에 프로그래밍 언어와 관계없이 알아두어야 할 필수 개념입니다.
본 강좌에서는 C#을 이용하여 유클리드 호제법을 구현하는 방법을 배워보겠습니다.

문제 설명

주어진 두 정수 a와 b에 대해, 두 수의 최대공약수(GCD)를 구하는 문제입니다.
GCD는 두 정수가 공통으로 가지는 최대의 양의 약수입니다.
예를 들어, a = 48, b = 18일 때, GCD(48, 18) = 6이 됩니다.

입력 형식

첫 번째 줄에 정수 a와 b가 공백으로 구분되어 주어진다 (1 ≤ a, b ≤ 10^9).

출력 형식

두 수 a와 b의 최대공약수(GCD)를 출력한다.

유클리드 호제법 이해하기

유클리드 호제법은 다음과 같은 원리를 기반으로 합니다:

1. 두 수 a와 b가 주어질 때, a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r) 입니다.
2. 이 과정을 반복하여 b가 0이 될 때, a가 GCD가 됩니다.

이러한 방법은 매우 효율적이며, 특히 a와 b이 큰 경우에도 빠르게 계산할 수 있습니다.
이러한 특성 덕분에 유클리드 호제법은 많은 알고리즘 문제에서 유용하게 사용됩니다.

C#으로 유클리드 호제법 구현하기

이제 C#을 이용해 유클리드 호제법을 구현해 보겠습니다. 아래는 해당 알고리즘을 구현한 코드입니다.


    using System;

    class Program
    {
        static void Main(string[] args)
        {
            // 입력값 받기
            string[] inputs = Console.ReadLine().Split(' ');
            int a = int.Parse(inputs[0]);
            int b = int.Parse(inputs[1]);

            // 최대공약수 계산
            int gcd = EuclideanGCD(a, b);
            Console.WriteLine(gcd);
        }

        static int EuclideanGCD(int a, int b)
        {
            while (b != 0)
            {
                int temp = b;
                b = a % b;  // 나머지를 구함
                a = temp;   // b의 값을 a에 대입
            }
            return a;  // GCD를 반환
        }
    }

코드 설명

위 코드는 두 정수를 입력받아 유클리드 호제법을 이용하여 최대공약수를 계산합니다.
Main 메서드에서는 사용자로부터 두 수를 입력받고, EuclideanGCD 메서드를 호출하여 GCD를 계산합니다.
EuclideanGCD 메서드는 while 루프를 사용하여 b가 0이 될 때까지 반복하며, GCD를 계산합니다.

시간 복잡도 및 공간 복잡도

유클리드 호제법의 시간 복잡도는 O(log(min(a, b)))입니다. 이는 두 수의 크기가 지수적으로 줄어들기 때문입니다.
공간 복잡도는 O(1)로, 추가적인 자료구조를 사용하지 않으므로 매우 효율적입니다.

테스트 케이스

알고리즘의 정확성을 검증하기 위해 다음과 같은 테스트 케이스를 사용해 볼 수 있습니다.


    // 테스트 케이스
    48 18  // 예상 출력: 6
    56 98  // 예상 출력: 14
    101 103 // 예상 출력: 1
    1000000000 500000000 // 예상 출력: 500000000

결론

유클리드 호제법은 최대공약수를 구하는 매우 효율적인 알고리즘입니다.
이번 글을 통해 C#을 사용하여 유클리드 호제법을 어떻게 구현할 수 있는지 살펴보았습니다.
코딩 테스트에서 이러한 알고리즘 문제를 자주 만나게 될 것이므로, 이해하고 연습하는 것이 중요합니다.

앞으로 다양한 알고리즘에 대한 심도 있는 강좌를 진행할 예정이니, 많은 관심 부탁드립니다!

서론