코테 - 최소공배수(LCM) 찾기 5가지 방법

최소공배수(LCM)는 두 숫자가 동시에 나누어지는 가장 작은 수입니다. 아래는 C 언어를 사용해 두 숫자의 LCM을 찾는 5가지 방법으로, 코딩 테스트 준비에 유용합니다.

방법 1: GCD를 이용한 LCM (유클리드 알고리즘 반복)

LCM(a,b) = (a * b) / GCD(a,b) 공식을 사용하며, GCD는 반복적 유클리드 알고리즘으로 계산합니다.

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(int a, int b) {
    return ((long long)a * b) / gcd(a, b);
}

int main() {
    int a = 12, b = 18;
    printf("LCM(%d, %d) = %lld\n", a, b, lcm(a, b));
    return 0;
}
        

방법 2: GCD를 이용한 LCM (유클리드 알고리즘 재귀)

재귀적 유클리드 알고리즘으로 GCD를 구한 후, LCM 공식을 적용합니다.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

long long lcm(int a, int b) {
    return ((long long)a * b) / gcd(a, b);
}

int main() {
    int a = 12, b = 18;
    printf("LCM(%d, %d) = %lld\n", a, b, lcm(a, b));
    return 0;
}
        

방법 3: 소인수분해를 통한 LCM

두 숫자의 소인수분해를 통해 공통 및 비공통 소인수를 곱하여 LCM을 계산합니다.

#include <stdio.h>

long long lcm(int a, int b) {
    int temp_a = a, temp_b = b;
    long long result = 1;
    for (int i = 2; i <= a || i <= b; i++) {
        int count_a = 0, count_b = 0;
        while (temp_a % i == 0) {
            count_a++;
            temp_a /= i;
        }
        while (temp_b % i == 0) {
            count_b++;
            temp_b /= i;
        }
        int max_count = count_a > count_b ? count_a : count_b;
        while (max_count--) result *= i;
    }
    return result;
}

int main() {
    int a = 12, b = 18;
    printf("LCM(%d, %d) = %lld\n", a, b, lcm(a, b));
    return 0;
}
        

방법 4: 이진 GCD를 이용한 LCM

이진 GCD 알고리즘(슈타인 알고리즘)으로 GCD를 구한 후, LCM 공식을 적용합니다.

#include <stdio.h>

int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    while ((a & 1) == 0) a >>= 1;
    while (b != 0) {
        while ((b & 1) == 0) b >>= 1;
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        b -= a;
    }
    return a << shift;
}

long long lcm(int a, int b) {
    return ((long long)a * b) / gcd(a, b);
}

int main() {
    int a = 12, b = 18;
    printf("LCM(%d, %d) = %lld\n", a, b, lcm(a, b));
    return 0;
}
        

방법 5: 배수 나열

두 숫자의 배수를 나열하여 첫 번째 공통 배수를 찾습니다. 비효율적이지만 직관적입니다.

#include <stdio.h>

long long lcm(int a, int b) {
    int max = a > b ? a : b;
    long long result = max;
    while (1) {
        if (result % a == 0 && result % b == 0) {
            return result;
        }
        result += max;
    }
}

int main() {
    int a = 12, b = 18;
    printf("LCM(%d, %d) = %lld\n", a, b, lcm(a, b));
    return 0;
}
        

각 방법은 시간 복잡도와 코드 단순성 측면에서 장단점이 있습니다. GCD를 이용한 방법(방법 1, 2, 4)은 효율적이고 코딩 테스트에서 선호됩니다. 소인수분해(방법 3)와 배수 나열(방법 5)은 직관적이지만 큰 숫자에서는 비효율적입니다.

설명

• 방법 1: GCD를 이용한 LCM (유클리드 알고리즘 반복): LCM(a,b) = (a * b) / GCD(a,b) 공식을 사용하며, GCD는 반복적 유클리드 알고리즘으로 계산. 시간 복잡도 O(log min(a,b)).
• 방법 2: GCD를 이용한 LCM (유클리드 알고리즘 재귀): GCD를 재귀적으로 계산하여 LCM을 구함. 코드가 간결하지만 스택 오버플로우 가능성 주의.
• 방법 3: 소인수분해를 통한 LCM: 두 숫자의 소인수분해에서 각 소인수의 최대 지수를 곱하여 LCM을 계산. O(min(a,b))로 비효율적.
• 방법 4: 이진 GCD를 이용한 LCM: 이진 GCD 알고리즘(슈타인)을 사용하여 GCD를 구한 후 LCM 계산. 비트 연산으로 나눗셈 연산 감소.
• 방법 5: 배수 나열: 두 숫자의 배수를 나열하여 첫 번째 공통 배수를 찾음. O(max(a,b) * min(a,b))로 매우 비효율적이나 이해하기 쉬움.

각 코드 예시는 a=12, b=18일 때 출력 예시: LCM(12, 18) = 36을 생성합니다. 코딩 테스트에서 요구되는 정확성과 효율성을 고려하여 작성되었으며, 특히 방법 1과 2가 가장 실용적입니다.