1. 서론
프로그래밍 대회나 코딩 테스트에서 자주 등장하는 문제 중 하나는 두 수의 최대 공약수(GCD, Greatest Common Divisor)를 구하는 문제입니다.
최대 공약수는 두 개의 자연수에서 공통으로 나누어 떨어지는 가장 큰 수를 의미합니다.
이 글에서는 C++을 사용하여 최대 공약수를 구하는 알고리즘을 설명하고, 문제를 해결하는 과정을 자세히 알아보겠습니다.
2. 문제 정의
두 개의 자연수 a와 b가 주어졌을 때, 이 두 수의 최대 공약수를 구하는 프로그램을 작성하시오.
입력으로 두 개의 자연수 a, b (1 <= a, b <= 1,000,000)가 주어지며, 결과로 최대 공약수 값을 출력해야 합니다.
예제 입력
48 18
예제 출력
6
3. 알고리즘 설명
최대 공약수를 구하는 방법에는 여러 가지가 있습니다.
여기서는 유클리드 호제법(Euclidean algorithm)을 사용하여 효율적으로 최대 공약수를 찾는 방법을 설명하겠습니다.
유클리드 호제법은 다음과 같은 원리를 기반으로 합니다.
두 수 a와 b의 최대 공약수 GCD(a, b)는 GCD(b, a mod b)와 같습니다.
이 과정을 반복하여 b가 0이 될 때까지 계속하면, a가 두 수의 최대 공약수가 됩니다.
즉, GCD(a, 0) = a이므로 마지막 남은 숫자가 최대 공약수입니다.
유클리드 호제법의 의사코드
function GCD(a, b):
while b ≠ 0:
temp := b
b := a mod b
a := temp
return a
4. C++ 코드 구현
위에서 설명한 알고리즘을 기반으로 C++로 최대 공약수(GCD)를 구하는 프로그램을 작성해보겠습니다.
다음은 해당 프로그램의 소스 코드입니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b;
cout << "두 개의 자연수를 입력하세요: ";
cin >> a >> b;
cout << "최대 공약수 (GCD): " << gcd(a, b) << endl;
return 0;
}
5. 코드 설명
위 코드는 다음과 같은 방식으로 작동합니다:
- 헤더 파일 포함:
#include <iostream>를 사용하여 입출력 스트림을 사용할 수 있도록 설정합니다. - gcd 함수 정의: 두 개의 정수 a, b를 매개변수로 받아 최대 공약수를 계산하는 함수를 정의합니다.
- 메인 함수: 사용자로부터 두 개의 자연수를 입력받고,
gcd함수를 호출하여 결과를 출력합니다.
6. 테스트 케이스
위에 작성한 코드가 올바르게 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 정의해보겠습니다.
테스트 케이스 1
입력
48 18
출력
6
테스트 케이스 2
입력
100 25
출력
25
테스트 케이스 3
입력
13 29
출력
1
7. 시간 복잡도 분석
유클리드 호제법의 시간 복잡도는 O(log(min(a, b)))입니다.
이는 두 수의 크기가 작아질수록 계산 시간이 줄어들기 때문입니다.
따라서 이 알고리즘은 효율적으로 최대 공약수를 계산할 수 있는 방법 중 하나입니다.
8. 결론
이번 글에서는 C++를 이용하여 최대 공약수를 구하는 방법에 대해 알아보았습니다.
유클리드 호제법을 사용하여 효과적으로 문제를 해결하는 과정을 살펴보았습니다.
알고리즘 문제 풀이에 있어, 이러한 기본적인 수학적 지식과 알고리즘은 매우 중요하니, 충분히 연습하고 숙지해두시길 권장합니다.