안녕하세요. 오늘은 최대공약수를 구하는 알고리즘을 소개하려고 합니다.
사실 키보드 몇 번 치고 금방 찾을 수 있는 간단한 알고리즘이지만, 한 번 생각을 정리하고자 작성합니다.
최대공약수를 구하는 알고리즘 중 가장 잘 알려진, 유클리드 호제법을 소개합니다.
먼저 최대공약수의 정의부터 짚고 넘어가겠습니다.
1. 최대공약수 (Greatest Common Divisor; GCD)
$$\text{두 정수의 공약수 중에서 가장 큰 공약수}$$
사실 이 정의만으로는 최대공약수를 정의하는데 부족함이 있을 순 있지만, 이해하는 데에는 어려움이 없기에 자세한 정의의 언급은 생략합니다.
2. 유클리드 호제법 (Euclidean algorithm)
$$a,b\in ℤ \text{이고, }a\text{를 }b\text{로 나눈 나머지를 }r\text{이라고 하고 }$$
$$a\text{와 }b\text{의 최대공약수를 }(a,b)\text{로 표현할 때}$$
$$(a,b)=(b,r)$$
위 유클리드 호제법을 어떻게 활용하느냐? \(84\)와 \(14\)의 최대공약수를 구하는 것으로 예시를 들어보겠습니다.
$$(168,52)=(52,12)=(12,4)=(4,0)=4$$
이때, \((4,0)\)의 의미는 앞전의 \((12,4)\)의 유일한 공약수는 4이라는 뜻으로, 결국은 \((168,52)=4\)이라고 알 수 있습니다.
정수에 대한 유클리드 호제법에 대한 증명은 이 링크를 통해 자세히 탐구할 수 있습니다.
3. 재귀함수와 유클리드 호제법을 이용한 최대공약수의 구현
그러면 이 알고리즘을 구현하도록 하겠습니다. 반복문을 이용한 방법과 재귀함수를 이용한 방법이 있습니다. 재귀함수의 구현이 훨씬 직관적이므로 재귀함수로 구현하고, 반복문을 통한 구현은 스스로 진행해보시길 바랍니다.
위 \((168,52)=(52,12)=(12,4)=(3,0)=3\) 를 보면 반복되는 큰 문제 \((168,52)\)와 동치인 작은 문제 \((52,12)\)를 쉽게 찾을 수 있습니다. 이러한 방식으로 재귀함수를 이어나가고, \((4,0)\) 같이 뒤의 수가 0이 나오는 경우에 return을 진행해주면 됩니다.
다음 소스코드를 참고하면 쉽게 이해할 수 있을 것입니다.
소스코드:
#include <stdio.h>
int gcd(int a, int b)
{
if(b==0)
return a;
else
gcd(b,a%b);
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d",gcd(a,b));
return 0;
}다음 게시물에서는 기존의 알려진 방법이 아닌, 조금 더 복잡하지만 신기한 저만의 방법을 들고 찾아오겠습니다.
감사합니다.