자바 코딩테스트 강좌, 유클리드 호제법

본 블로그 글에서는 자바 코딩 테스트에서 자주 등장하는 유클리드 호제법에 대해 살펴보겠습니다. 유클리드 호제법은 두 수의 최대 공약수를 효율적으로 구할 수 있는 알고리즘으로, 기초적인 수학 지식이 필요한 문제입니다. 이 글에서는 유클리드 호제법을 이용한 알고리즘 문제를 제시하고, 그 해결 과정을 자세하게 설명하겠습니다.

문제 설명

유클리드 호제법 소개

유클리드 호제법은 고대 그리스의 수학자 유클리드(Euclid)가 고안한 방법으로, 주어진 두 수의 최대 공약수를 구하는 알고리즘입니다. 두 수 A와 B가 주어졌을 때, GCD(A, B)는 GCD(B, A % B)와 같다는 성질을 이용합니다. 이 과정은 A가 0이 될 때까지 반복되며, 최종적으로 B의 값이 GCD가 됩니다.

유클리드 호제법의 알고리즘

1. A가 0이 아닐 경우: GCD(A, B) = GCD(B % A, A)
2. A가 0일 경우: GCD(A, B) = B

위 알고리즘을 코딩에 적용하여 문제를 해결해보겠습니다.

문제 풀이

1단계: 함수를 설계하자

먼저 두 수의 최대 공약수를 구하는 함수를 설계합니다. 우리는 재귀 함수를 사용할 것입니다.

public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

위 코드는 두 정수 A와 B를 인자로 받아 최대 공약수를 재귀적으로 계산합니다. B가 0일 경우 A가 최대 공약수입니다. 그 외의 경우에는 GCD(B, A % B)를 호출하여 최대 공약수를 계속 계산합니다.

2단계: 메인 함수 작성

이제 메인 함수를 작성하여 입력을 처리하고, 앞서 만든 GCD 함수를 호출하도록 합니다.

import java.util.Scanner;

public class GCDExample {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("두 정수를 입력하세요 (A B): ");
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        int result = gcd(a, b);
        System.out.println("두 수 " + a + "와 " + b + "의 최대 공약수는: " + result);
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

위 코드는 사용자로부터 두 수를 입력받아 최대 공약수를 계산하고 출력합니다. Scanner 클래스를 사용하여 입력을 받고, gcd 메서드를 호출하여 계산 결과를 얻습니다.

3단계: 코드 테스트

이제 프로그램을 실행하여 두 수의 최대 공약수를 계산해 보겠습니다. 예를 들어 48과 18을 입력하면, 다음과 같은 결과가 출력됩니다.

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

최적화 및 추가 사항

유클리드 호제법은 매우 효율적인 알고리즘으로, 시간 복잡도는 O(log(min(A, B)))입니다. 그러나 주어진 문제에서 더 다양한 활용 방법이나 성능 최적화를 고려할 수도 있습니다.

최대 공약수 배열의 활용

예를 들어, 여러 수의 배열이 있는 경우 여러 수의 최대 공약수를 구하는 방법도 생각해볼 수 있습니다. 이는 아래와 같은 형태로 구현 가능합니다.

public static int gcdArray(int[] numbers) {
    int result = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        result = gcd(result, numbers[i]);
    }
    return result;
}

위 메서드는 정수 배열을 인자로 받아, 배열 내 모든 수의 최대 공약수를 계산합니다.

결론

이번 글에서는 유클리드 호제법을 활용하여 최대 공약수를 구하는 문제를 해결해 보았습니다. 이 알고리즘은 코딩 테스트에서 빈번히 등장하며, 후보자들의 문제 해결 능력을 평가하는 데 좋은 도구가 됩니다. 입력에 대한 적절한 처리를 통해 다양한 크기의 수에 대해서도 안정적으로 동작하는 프로그램을 작성할 수 있음을 보여주었습니다.

이와 같은 알고리즘 문제를 체계적으로 정리하고 실습하는 것은 여러분이 코딩 테스트에 대비하는 데 큰 도움이 될 것입니다. 어려운 문제를 접했을 때도 유연하게 대처할 수 있도록 다양한 문제를 연습하면서 실력을 닦아 나가시기 바랍니다.

참고 자료

• Euclidean Algorithm – Wikipedia