개요
이 튜토리얼에서는 반복문(iteration)을 사용하여 두 수의 HCF(Highest Common Factor, 최대공약수)를 구하는 C++ 프로그램을 다룹니다.
HCF란 두 수를 모두 나누어 떨어지게 하는 가장 큰 양의 정수를 의미합니다. 예를 들어 60과 96의 경우, 두 수를 모두 나눌 수 있는 가장 큰 수는 12이므로 HCF는 12가 됩니다.
알고리즘 원리
여기서 사용하는 방식은 유클리드 호제법(Euclidean algorithm)의 뺄셈 기반 버전으로, 재귀 호출 없이 while 반복문만으로 해결할 수 있습니다. 동작 과정은 다음과 같습니다.
- 두 수가 서로 같아질 때까지 반복합니다.
- a가 b보다 크면 a에서 b를 빼고, 그렇지 않으면 b에서 a를 뺍니다.
- 반복이 끝나 두 수가 같아지면 그 값이 곧 HCF입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int get_HCF(int a, int b){
while (a != b){
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
int main(){
int a = 60, b = 96;
cout << get_HCF(a, b) << endl;
return 0;
}
실행 결과
12
코드 설명
get_HCF 함수는 매개변수로 받은 두 정수 a와 b가 같아질 때까지 while 루프를 돌며 큰 값에서 작은 값을 계속 빼 줍니다. 이 과정을 거치면 두 값은 자연스럽게 최대공약수로 수렴하게 되며, 루프가 종료되는 시점의 a값이 바로 HCF입니다.
main 함수에서는 60과 96을 인자로 넘겨 결과를 출력하며, 위 코드를 실행하면 12가 출력되는 것을 확인할 수 있습니다.
참고 사항
뺄셈 기반 방식은 이해하기 쉽다는 장점이 있지만, 두 수의 차이가 클 경우 반복 횟수가 많아져 비효율적일 수 있습니다. 실무에서는 나머지 연산(%)을 활용한 유클리드 호제법을 사용하면 훨씬 빠르게 결과를 얻을 수 있습니다.