C++ 코딩테스트 강좌, 최소 공배수 구하기

1. 문제 설명

주어진 두 정수 A와 B에 대해 A와 B의 최소 공배수(Least Common Multiple, LCM)를 구하는 문제입니다. 최소 공배수는 두 수의 배수 중에서 가장 작은 수를 의미합니다. 예를 들어, 4와 5의 최소 공배수는 20입니다.

2. 입력 형식

첫 번째 줄에 정수 A와 B가 주어집니다. (1 ≤ A, B ≤ 10⁶)

3. 출력 형식

주어진 정수 A와 B의 최소 공배수를 출력합니다.

4. 문제 예시

5. 알고리즘 설계

최소 공배수를 구하는 일반적인 방법은 두 수의 최대 공약수를 사용하는 것입니다. 다음은 이론입니다.

최소 공배수는 다음과 같이 계산할 수 있습니다:

    LCM(A, B) = (A * B) / GCD(A, B)

여기서 GCD는 최대 공약수(Greatest Common Divisor)를 의미합니다. 이를 계산하기 위해 유클리드 알고리즘을 사용할 수 있습니다.

5.1 유클리드 알고리즘

유클리드 알고리즘은 두 수의 GCD를 구하기 위한 고전적인 방법으로, 다음과 같이 작동합니다:

두 수 A와 B 중에서 B가 0이 아닐 경우, A를 B로 나눈 나머지를 C로 저장합니다.
A를 B로, B를 C로 업데이트합니다.
이 과정을 B가 0이 될 때까지 반복합니다.
최종적으로 A가 GCD입니다.

6. C++ 코드 구현

이제 최종적으로 C++에서 최소 공배수를 구하는 코드를 구현해보겠습니다.


#include <iostream>
using namespace std;

// 최대 공약수 (GCD) 계산
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 최소 공배수 (LCM) 계산
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int A, B;
    cout << "두 정수 A와 B를 입력하세요: ";
    cin >> A >> B;

    int result = lcm(A, B);
    cout << "최소 공배수는: " << result << endl;
    return 0;
}

7. 코드 설명

위 코드는 세 가지 주요 부분으로 나눌 수 있습니다:

gcd 함수: 두 정수 A와 B의 최대 공약수를 계산합니다.
lcm 함수: 두 정수의 최소 공배수를 계산하는 역할을 합니다.
main 함수: 프로그램의 진입점으로, 사용자로부터 입력을 받아 최소 공배수를 출력합니다.

8. 테스트 및 검증

코드를 실제로 테스트하기 위해 다양한 입력 값을 사용하여 올바른 결과를 검증해야 합니다.

    입력: 4 5
    출력: 20

    입력: 12 15
    출력: 60

    입력: 7 3
    출력: 21

    입력: 21 14
    출력: 42

    입력: 1 1000000
    출력: 1000000

이러한 다양한 테스트 케이스를 통해 코드의 정확성과 안정성을 검증할 수 있습니다.

9. 성능 고려

최소 공배수 계산은 일반적으로 두 수의 곱의 값을 최대 공약수로 나누기 때문에, 실제 성능은 GCD 알고리즘의 성능에 큰 영향을 받습니다. 유클리드 알고리즘은 O(log(min(A, B)))의 시간 복잡도를 가지므로, 입력 크기에 비례하여 효율적으로 동작합니다.

10. 결론

이번 강좌에서는 두 정수의 최소 공배수를 구하는 방법에 대해 알아보았습니다. 유클리드 알고리즘을 이용한 최대 공약수 계산과 이를 활용한 최소 공배수 계산 방법을 배웠습니다. 이 알고리즘은 다양한 문제 해결에 응용될 수 있으므로, 유용한 기초 지식이 될 것입니다.