[java]최대공약수 최소공배수

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int big = Math.max(n, m);
        int small = Math.min(n, m);
        
        answer[0] = gcd(big, small); // 최대공약수 계산
        answer[1] = lcm(big, small); // 최소공배수 계산
        
        return answer;
    }
    
    // 최대공약수 계산 (유클리드 호제법 사용)
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // 최소공배수 계산 (두 수의 곱 / 최대공약수)
    private int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

유클리드 호제법은 두 개의 정수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 데 사용되는 알고리즘입니다. 이 방법은 기원전 300년에 고대 그리스 수학자인 유클리드에 의해 개발되었습니다.

유클리드 호제법은 다음과 같은 아이디어에 기반합니다:

두 수 a와 b의 최대공약수는 a를 b로 나눈 나머지(r)의 최대공약수와 동일합니다.
만약 r이 0이라면, b가 a의 최대공약수입니다.
이 원리를 반복해서 적용하면 최종적으로 나머지가 0이 되는 순간, 나누는 수가 최대공약수가 됩니다.

간단한 예시를 통해 이해해보겠습니다:

두 수 48과 18의 최대공약수를 구해보겠습니다.

48을 18로 나누면 나머지는 12가 됩니다.
이제 18을 12로 나누면 나머지는 6이 됩니다.
다시 12를 6으로 나누면 나머지는 0이 됩니다.
나머지가 0이 되었을 때의 나누는 수인 6이 최대공약수입니다. 따라서 48과 18의 최대공약수는 6입니다.

유클리드 호제법은 간단하면서도 효과적인 알고리즘이며, 최대공약수를 빠르게 계산하는 데에 널리 사용됩니다.