🚑 유클리드 호제법이란?
유클리드 호제법 / Euclidean alogorithm
두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로 말에서 나오듯이 호제법이란 서로 호(互) 덜 제(除)라는 의미로 즉, 서로 나눈다는 볼 수 있다.
※ 유클리드 호제법이 인류 최초의 알고리즘이라고 한다.
😒 유클리드 호제법의 공식
위키의 내용을 발췌한 것이다. 말이 어렵다.. 그래서 이를 같이 풀어보자
a = bq + r(0<= r < b)이라고 하면 다음과 같다고 하는데,
여기서 q는 a와 b를 나눈 몫을 의미하며 r은 나머지의 값을 말한다.
즉, a = 15 / b = 6이라고 가정하자, 그렇다면 15 = 6 * 2(15 / 6) + 3(15 % 6)으로 구할 수 있는 것이다.
그럼 해당 가정은 맞으니 뒤로 넘어가 a, b의 최대공약수는 b,r의 최대공약수와 같다고 한다.
이를 풀어보면 6 = {1, 2, 3, 6} 3 = {1, 3} 6과 3의 최대공약수는 3
a, b의 최대공약수는 15 = {1, 3, 5, 15} 6 = {1, 2, 3, 6} 15와 6의 최대공약수 역시 3이다.
아하! 그렇다면 gcd(a, b) = gcd(b, r)이 성립할 수 있다는 것이다.
그래서 이를 r = 0이 될 때까지 반복하면 a, b의 최대공약수는 b가 될 수 있는 것이다.
자 그럼 한번 실습을 해보도록 하겠다. (수가 작으니 간단히 살펴보자)
1. gcd(15, 6) = gcd(6, 3)
2. gcd(6, 3) = gcd(3 , 0) -> r이 0이 되고 b값만 존재하는데 이게 a,b의 최대공약수인 것이다.
잠깐! 여기서 gcd란?
GCD란 Greatest Common Divisor라는 말로 공통된 가장 큰 약수라는 의미다.
그럼 한 마디로 최대공약수다.
😢 유클리드 호제법 증명
그럼 왜 이게 맞는지 같이 증명해보자,
여기서 a와 b의 공약수를 d라고 하면 gcd(a, b) = d, gcd(b, r) = d` 로 구할 수 있다.
그렇다면, 이를 수식으로 보면
a = A * d , b = B * d 즉, a= Ad b= Bd 로 구할 수 있다.
※여기서 A와 B는 서로소이다. (서로소란: 두 수의 공약수가 1밖에 없다는 의미이다)
아까 위에서 가져온 Tc값 a= 15 , b = 6을 대입해보자,
a = 5 * 3 , b = 2 * 3 일때 5와 2의 공약수는 1밖에 존재하지 않는다. 그래서 서로소인 것이다.
자 이제 위에서 구한 값을 a = bq + r에 대입시켜보자,
그러면 Ad = Bdq + r 이고 r = d(A - Bq)이다.
여기서 우리는 b = Bd이고 r = d(A - Bq)로 b와 r은 d를 공통된 약수로 갖기에 d는 b와 r의 공약수라고 할 수 있는 것이다.
머리로는 이해가 가는데 설명이 잘 안된다 즉, d를 공약수라고 가정하고 넣었을 때
b = Bd , r= d(A - Bq) 를 가지기 때문에 우리는 b, r의 공약수도 d라고 볼 수 있다는 얘기다.
여기까지 위키를 보면서 이해한 바이다. 하지만, 타 블로그를 참조하면서 보니, d가 최대공약수라는 증명이 되지 않았기에 뒤에 더 내용이 존재한다.
수포자의 머리로 설명을 매끄럽지 않아 증명은 여기까지 마무리 하겠다
✌ 요약 정리
짧으면 짧은 유클리드 호제법 정리는 끝났고, 이를 요약해서 정리해 보여드린다면,
a,b의 값이 존재하며(a > b) a = bq + r 이라면 a, b 와 b r의 최대공약수는 같다.
즉, 이를 r이 0이 될 때까지 반복하면 결국 gcd(a, b)의 최대 공약수는 gcd(b,0) -> b 가 된다.
😊 코드로 보는 유클리드 호제법
사실 해당 세션을 위해 이번 유클리드 호제법을 정리하였다.
필자는 Java를 주로 다루기 때문에 Java코드만 정리하여 올려보겠다.
(그래도 다양한 언어 공부를 지향합니다 ㅎ)
static int gcd(int A, int B) {
while(B != 0) {
int r = A % B;
A = B;
B = r;
}
return A;
}이는 자바코드와 반복문을 활용한 gcd를 구하는 방법이다.
static int gcd(int A, int B) {
if (r == 0) {
return A;
}
int r = A % B;
return gcd(B, r);
}이는 자바코드와 재귀함수를 활용한 gcd를 구하는 방법이다.
아! 유클리드 호제법의 시간 복잡도는 O(log N)으로 이를 좀 더 자세히 설명하면
O(log min(A, B))의 시간 복잡도를 가진다고 한다.
👏 잠깐!. 그렇다면 최소공배수는..
염치없이 최대공약수를 구하는거 까지만 했다. 물론 유클리드 호제법이 최대공약수를 구하는 방법이니깐..
최소공배수는 간단하다.
양의 정수 A, B가 존재한다면 A * B / d(gcd를 통해 나온 최대공약수) 를 해주면 최소공배수를 구할 수 있다.
💜 참고자료
