C# 코딩테스트 강좌, 최대 공약수 구하기

알고리즘 문제는 취업 준비를 하는 많은 사람들에게 중요한 시험 범위 중 하나입니다. 이번 강좌에서는 C#을 이용하여 최대 공약수(Greatest Common Divisor, GCD)를 구하는 방법을 함께 알아보겠습니다. 최대 공약수는 두 정수를 나누고 나서 나머지가 0이 되는 가장 큰 수를 뜻합니다.

문제 설명

두 정수 A와 B가 주어졌을 때, 이 두 수의 최대 공약수를 구하시오.

예제 입력:
A = 48, B = 18

예제 출력:
GCD = 6

최대 공약수의 개념

최대 공약수는 두 개 이상의 정수에서 공통적으로 나누어 떨어지는 가장 큰 정수를 의미합니다. 예를 들어, 48과 18의 공약수는 1, 2, 3, 6, 9, 18입니다. 이 중 가장 큰 수인 6이 두 수의 최대 공약수입니다.

최대 공약수를 구하는 알고리즘

최대 공약수를 구하는 방법으로는 여러 가지가 있지만, 여기서는 유클리드 호제법을 이용한 방법을 설명하겠습니다. 이 방법은 다음과 같은 절차로 이루어집니다:

두 정수 A와 B가 주어졌을 때, B가 0이 아닐 경우 다음을 반복합니다.
A를 B로 나눈 나머지를 구합니다. (즉, R = A % B)
A를 B로, B를 R로 바꿉니다.
B가 0이 될 때까지 이 과정을 반복합니다.
B가 0이 되었을 때, A가 최대 공약수입니다.

C# 코드 구현

이제 위의 알고리즘을 C# 코드로 구현해보겠습니다. 아래 코드는 최대 공약수를 구하는 간단한 프로그램입니다.


using System;

class Program
{
    static void Main(string[] args)
    {
        Console.Write("A를 입력하세요: ");
        int A = int.Parse(Console.ReadLine());

        Console.Write("B를 입력하세요: ");
        int B = int.Parse(Console.ReadLine());
        
        int gcd = GetGCD(A, B);
        Console.WriteLine($"최대 공약수(GCD)는: {gcd}");
    }

    static int GetGCD(int a, int b)
    {
        while (b != 0)
        {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

위 코드는 사용자가 두 개의 정수 A와 B를 입력하도록 하고, GetGCD 메서드를 통해 최대 공약수를 계산하여 출력합니다.

코드 설명

– using System; : System 네임스페이스를 사용하여 콘솔 입출력을 처리합니다.
– Main 메서드 : 프로그램의 시작점으로, 사용자로부터 두 개의 정수를 입력받습니다.
– GetGCD 메서드 : 유클리드 호제법을 사용하여 최대 공약수를 계산합니다. 이 메서드는 두 정수를 인자로 받아, 반복문을 통해 공약수를 구합니다.

실행 예시

실행 결과를 살펴보겠습니다. 사용자가 입력한 두 수가 48과 18일 경우:

A를 입력하세요: 48
B를 입력하세요: 18
최대 공약수(GCD)는: 6

테스트 및 예외 처리

실제 프로그램을 사용할 때는 다양한 입력에 대해 테스트를 진행해야 합니다. 정수가 아닌 값을 입력했을 경우를 고려한 예외 처리가 필요합니다. 아래 코드는 예외 처리를 추가한 예시입니다.


using System;

class Program
{
    static void Main(string[] args)
    {
        try
        {
            Console.Write("A를 입력하세요: ");
            int A = int.Parse(Console.ReadLine());

            Console.Write("B를 입력하세요: ");
            int B = int.Parse(Console.ReadLine());
            
            int gcd = GetGCD(A, B);
            Console.WriteLine($"최대 공약수(GCD)는: {gcd}");
        }
        catch (FormatException)
        {
            Console.WriteLine("유효한 정수를 입력하세요.");
        }
    }

    static int GetGCD(int a, int b)
    {
        while (b != 0)
        {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

위의 코드에서는 try-catch 블록을 사용하여 입력값이 정수가 아닐 경우를 처리합니다. FormatException이 발생하면 사용자에게 유효한 정수를 입력하라고 안내합니다.

마무리 및 추가 학습 자료

이번 강좌에서는 C#을 이용하여 최대 공약수를 구하는 알고리즘을 구현하고, 유클리드 호제법을 기반으로 한 방법을 소개했습니다. 알고리즘 문제는 취업 준비에 많은 도움이 되므로, 다양한 문제를 지속적으로 풀어보는 것을 추천드립니다. 다음에는 다른 알고리즘 문제를 다룰 예정입니다.

추가로 추천하는 학습 자료로는 다음과 같은 사이트들을 소개합니다:

GeeksforGeeks – 다양한 자료구조와 알고리즘 문제 풀이
LeetCode – 코딩 테스트 및 알고리즘 문제 풀이 플랫폼
HackerRank – 알고리즘 문제와 코딩 테스트를 위한 사이트

피드백 및 질문

본 강좌에 대한 피드백이나 질문이 있으시면 언제든지 댓글로 남겨주세요. 최선을 다해 답변드리겠습니다. 감사합니다!