[Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 유클리드 호제법에 대해서 알아보고 코드로 구현해보겠습니다.

그리고 추가적으로 백준 온라인 저지에 있는 BOJ 2609번 최대공약수 문제도 같이 풀어보겠습니다.

 

1. 유클리드 호제법이란? (Euclidean Algorithm)

1.1 개념

유클리드 호제법은 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다.

일반적으로 우리가 수학을 배울 때, 두 수 사이의 최대공약수는 소인수분해를 하고 소인수들의 곱으로 구할 수 있었습니다.

소인수분해를 물론 코드로 구현할 수는 있겠지만 효율적이지는 않을 겁니다.

왜냐하면 우선 소인수분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두 개의 수를 공통적으로 나눌 수 있는지를 확인을 해야 하기 때문입니다.

만약 주어진 두 개의 수가 매우 크다면 시간 복잡도는 계속 증가할 테니까요

유클리드 호제법 알고리즘을 사용하면 이러한 문제를 쉽게 해결할 수 있습니다.

유클리드 호제법의 기본개념은 다음과 같습니다.

두 개의 수 A, B가 존재하고, A를 B로 나눈 나머지를 C라고 하겠습니다. (A > B)

이때, A와 B의 최대공약수는 B와 C의 최대공약수와 같습니다. (왜 그런지는 증명을 찾아보시길!)

이러한 성질을 이용해서 계속적으로 나눗셈을 진행해서 C가 0이 되었을 때, 즉 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 됩니다.

이러한 이론적인 말로는 이해가 잘 되지 않으실 테니 예시를 들어서 한번 표현해보겠습니다.

 

1.2 예시

72, 42 두 개의 수로 유클리드 호제법을 사용해서 최대공약수를 구해보겠습니다.

1. 먼저 두 개의 수 중 큰 수를 찾습니다. 여기서는 72입니다.
2. 큰 수를 작은 수로 나눠서 나머지를 구합니다. => 72 % 42 = 30(나머지)
3. 나머지를 가지고 앞에서 나눈 수를 다시 나눠서 나머지를 구합니다. => 42 % 30 = 12(나머지)
4. 3번의 과정을 반복합니다. => 30 % 12 = 6(나머지)
5. 3번의 과정을 반복합니다. => 12 % 6 = 0(나머지)
6. 5번의 과정을 마지막으로 나머지가 0이 되었으므로 그 시점에 나눈 수가 최대공약수가 됩니다.
7. 위의 순서대로라면 72와 42의 최대공약수는 6이 됩니다.

직접 식으로 보시니까 이해하기 수월해지셨나요?

그럼 이번에는 코드로 구현해보겠습니다.

 

2. Java로 유클리드 호제법 구현

유클리드 호제법은 나머지가 0이 되는 시점까지 계속해서 동일한 연산을 진행해야 합니다.

몇 번의 반복을 통해서 나머지가 0이 되는지 알 수 없으므로 반복문으로 구현하는 것이 아니라 재귀 형태로 구현을 해야 합니다.

구현 코드는 다음과 같습니다.

/**
     * 유클리드 호제법 구현 메서드
     * @param bn : 큰 숫자
     * @param sn : 작은 숫자
     * @return
     * 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
     */
    public int eucd(int bn, int sn) {
        // 큰숫자를 작은숫자로 나눈 나머지를 계산
        int r = bn % sn;
        // 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
        if (r == 0) {
            return sn;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자와 나머지를 넣어줌
            return eucd(sn, r);
        }
    }

코드에 라인마다 주석을 달아놓았으니 읽어보시면 바로 이해되실 겁니다.

생각보다 코드가 매우 간단하므로 이해가 잘 되지 않으시면 직접 숫자를 대입해보시면 이해하시는데 도움이 될 것 같습니다.

그럼 유클리드 호제법을 사용해서 실제 알고리즘 문제를 풀어보겠습니다.

 

3. BOJ-2609번 최대공약수와 최소공배수 문제 풀이

3.1 문제 설명

설명을 진행하기에 앞서 아래에 문제 링크가 있으니 문제를 읽고 와주시길 바랍니다.

https://www.acmicpc.net/problem/2609

 

문제는 두 개의 수가 주어졌을 때 최대공약수와 최소공배수를 구하면 되는 문제입니다.

최대공약수는 유클리드 호제법을 사용해서 구할 수 있을 텐데 최소공배수는 어떻게 구할까요??

다음과 같은 식을 통해서 구할 수 있습니다.

최소공배수 = 최대공약수 * (수 1 / 최대공약수) * (수 2/ 최대공약수)

즉, 2개의 수 모두 최대공약수로 나눠서 얻은 수와 최대공약수 3개의 수를 모두 곱하면 됩니다.

왜 그런지는 소인수분해를 직접 해보시면 바로 알 수 있을 겁니다.

그럼 코드를 살펴보겠습니다.

 

3.2 Java코드로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.util.Scanner;

public class BOJ_2609 {

    // 백준온라인저지 2609번 최대공약수와 최소공배수 Java로 문제풀이
    public static void main(String[] args) {

        // 주어진 입력정보 받기
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();

        // 유클리드 호제법을 사용해서 두수의 최대공약수 얻기
        int N = eucd(Math.max(A, B), Math.min(A, B));

        // 최대공약수로 두수를 나눠서 몫 구하기
        A = A / N;
        B = B / N;

        // 두 수의 최소공배수 = 두 수의 최대 공약수 * 위에서 구한 몫
        int M = A * B * N;

        // 출력
        System.out.println(N);
        System.out.println(M);
    }

    /**
     * 유클리드 호제법 구현 메서드
     * @param bn : 큰 숫자
     * @param sn : 작은 숫자
     * @return
     * 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
     */
    static int eucd(int bn, int sn) {
        // 큰숫자를 작은숫자로 나눈 나머지를 계산
        int r = bn % sn;
        // 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
        if (r == 0) {
            return sn;
        } else {
            // 나머지가 0 이상이면 재귀형태로 호출
            // 이때 파라미터는 작은숫자와 나머지를 넣어줌
            return eucd(sn, r);
        }
    }

}

코드의 라인별로 주석을 모두 달아놓았으니 천천히 읽어보시길 바랍니다.

감사합니다.

---