1. 문제 설명
주어진 두 정수 A와 B에 대해 A와 B의 최소 공배수(Least Common Multiple, LCM)를 구하는 문제입니다. 최소 공배수는 두 수의 배수 중에서 가장 작은 수를 의미합니다. 예를 들어, 4와 5의 최소 공배수는 20입니다.
2. 입력 형식
첫 번째 줄에 정수 A와 B가 주어집니다. (1 ≤ A, B ≤ 106)
3. 출력 형식
주어진 정수 A와 B의 최소 공배수를 출력합니다.
4. 문제 예시
입력:
4 5
출력:
20
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. 결론
이번 강좌에서는 두 정수의 최소 공배수를 구하는 방법에 대해 알아보았습니다. 유클리드 알고리즘을 이용한 최대 공약수 계산과 이를 활용한 최소 공배수 계산 방법을 배웠습니다. 이 알고리즘은 다양한 문제 해결에 응용될 수 있으므로, 유용한 기초 지식이 될 것입니다.