최대 공약수, 최소 공배수

1. 최대공약수 (GCD - Greatest Common Divisor)

'유클리드 호제법'을 사용합니다. 두 수를 나누어 그 나머지를 계속해서 나누는 과정을 나머지가 0이 될 때까지 반복합니다. 코테에서는 보통 코드가 훨씬 짧은 재귀 방식을 애용합니다.

Java

// 1. 재귀 방식 (코딩 테스트 강력 추천)
static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 2. 반복문 방식 (메모리나 재귀 깊이가 걱정될 때)
static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

2. 최소공배수 (LCM - Least Common Multiple)

**"두 수의 곱을 최대공약수로 나눈다"**라는 절대 공식만 기억하시면 됩니다.

Java

 

// 최소공배수 공식: (A * B) / GCD
static int lcm(int a, int b) {
    // 주의: a * b를 먼저 하면 int 범위를 초과(오버플로우)할 수 있습니다.
    // 안전하게 a를 gcd로 먼저 나누고 b를 곱하는 방식을 추천합니다!
    return (a / gcd(a, b)) * b; 
}

💡 실전 팁: 만약 문제에서 주어지는 숫자 a, b의 크기가 10만 단위를 넘어간다면, 곱하는 과정에서 int 범위를 뚫고 나갈 수 있으니 안전하게 long 타입으로 선언해서 푸는 것이 가장 마음 편합니다.