반응형
유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요.
유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다.
여담으로 최소공배수는 (두 수의 곱/gcd)를 하면 되기 때문에, 따로 구할 필요가 없고
세 수의 최대공약수를 구한다 해도 gcd(gcd(a,b),c)를 하면 되므로 두 수의 최대공약수를 구하는 알고리즘에 대해서만 알아도 충분할 겁니다.
우선 위의 사진에서 최대공약수를 구하는 알고리즘을 이해할 수 있고,
이는 단순히 r = a%b 에 대해서 gcd(a,b) = gcd(b,r)임을 보이면 됩니다.
증명은 위와 같습니다.
그래서 gcd함수 부분을 코드로 구현하면
int gcd(int a, int b)
{
if(b == 0)
{
return a;
}
return gcd(b,a%b);
}
이와 같은데, 저는 재귀가 보기도 편해서 이렇게 구현해서 사용합니다.
확장된 유클리드 알고리즘이라는 것도 있는데 이는 부정방정식의 해를 구할 때 사용합니다. 고등학생 때 확장된 유클리드 알고리즘으로 일차 선형 부정방정식을 게산하는걸 만들었는데 이젠 기억이 안 나네요..
감사합니다.
반응형
