[백준] 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

 

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

 

문제 풀이

나는 문제를 풀면서 알고리즘에 대해 거의 모르기 때문에 무작정 조건에 맞춰서 최대공약수와 최소공배수를 구하기에 바빴다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int num1 = in.nextInt();
        int num2 = in.nextInt();
        int a = 0; // 최대공약수
        int b = 0; // 최소공배수

        ArrayList<Integer> list1 = new ArrayList<>(); // num1의 약수
        ArrayList<Integer> list2 = new ArrayList<>(); // num2의 약수

        // num1의 약수
        for (int i = 1; i <= num1; i++) {
            if (num1 % i == 0) {
                list1.add(i);
            }
        }
//        System.out.println(list1);

        // num2의 약수
        for (int i = 1; i <= num2; i++) {
            if (num2 % i == 0) {
                list2.add(i);
            }
        }
//        System.out.println(list2);

        // 최대공약수
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1.get(i) == list2.get(j)) {
                    a = list1.get(i);
                }
            }
        }
        System.out.println(a);

        // 최소공배수
        int x = list2.get(list2.size() - 1);
        for (int i = 1; i <= list1.size(); i++) {
            if (x % i != 0) {
                b = x * i;
                break;
            }
        }
        System.out.println(b);
    }
}

그래서 이렇게 풀었다.

우선 최대공약수는 나름 잘 설계했다고 생각했다. 하지만 최소공배수를 구하는 과정에서 확신이 들지 않았다.
단순히 문제에 입력되어있는 예제인 24, 18의 최소공배수를 억지로 맞추기 위한 것 같았다.

그러다가 유클리드 알고리즘이 있다는 사실을 알게되었다.
유클리드 알고리즘으로 최대공약수를 구하고, 그렇게 구한 최대공약수로 최소공배수를 구할 수 있는 것이다.

유클리드 알고리즘은 다음과 같은 원리를 갖고 있다.

 

유클리드 알고리즘의 기본 원리

1. 두 수 A와 B가 있을 때 (A ≥ B라고 가정), A를 B로 나눈 나머지를 R이라고 합니다.
2. A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
3. 이 과정을 R이 0이 될 때까지 반복합니다.
4. R이 0이 되면, 그때의 B가 원래 두 수의 최대공약수입니다.

이 알고리즘이 효율적인 이유는 모든 약수를 찾아 비교할 필요 없이, 단순한 나눗셈 연산만으로 최대공약수를 빠르게 찾을 수 있기 때문이다. 시간 복잡도는 대략 O(log(min(a,b)))로, 매우 큰 수에 대해서도 빠르게 동작합니다.
나는 모든 약수를 찾아 비교하는 방식을 사용했다면, 유클리드 알고리즘은 이 과정을 거치지 않아도 된다.

유클리드 알고리즘을 이용해서 푼 코드는 다음과 같다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int num1 = in.nextInt();
        int num2 = in.nextInt();

        // 최대공약수 (GCD) 계산
        int gcd = findGCD(num1, num2);
        System.out.println(gcd);

        // 최소공배수 (LCM) 계산
        int lcm = (num1 * num2) / gcd;
        System.out.println(lcm);
    }

    // 유클리드 알고리즘을 사용한 최대공약수 계산
    public static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

유클리드 알고리즘을 알면 다른 응용 문제들에도 쉽게 접근할 수 있을 것 같아 대해 더 많이 공부해봐야겠다.