알고리즘 문제

public class Solution 
{
    // 두 자연수 n과 m을 받아 최대공약수와 최소공배수를 반환하는 함수
    public int[] solution(int n, int m) 
    {
        // 최대공약수(GCD)를 구함
        int gcd = GCD(n, m);
        
        // 최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눈 것
        int lcm = (n * m) / gcd;

        // 결과 배열: [최대공약수, 최소공배수]
        return new int[] { gcd, lcm };
    }

    // 최대공약수를 구하는 재귀 함수 (유클리드 호제법 사용)
    private int GCD(int a, int b) 
    {
        // b가 0이면 a가 최대공약수
        if (b == 0)
            return a;
        else
            // GCD(a, b) = GCD(b, a % b)
            return GCD(b, a % b);
    }
}

해석 

• solution(int n, int m):
  • 두 수 n, m의 최대공약수(GCD)를 먼저 구하고,
  • 이를 이용해 최소공배수(LCM)를 계산.
  • 결과는 [GCD, LCM] 형식의 배열로 반환.
• GCD(int a, int b):
  • 유클리드 알고리즘을 사용한 재귀 함수.
  • b가 0이 될 때까지 GCD(b, a % b)를 반복하며 계산.