유클리드 호제법이란
유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.
호제(互除)
일단 호제법이라는 말부터 무슨 소리인가 싶다.
서로 호(互), 나눌 제(除), 즉 서로 번갈아가면서 나누는 방법이라는 뜻이다.
뭘 번갈아가면서 나눈다는걸까?
숫자 a, b의 최대공약수를 구하는 함수 gcd(a, b)가 있다고 해보자(a가 b보다 크다).
그러면 gcd(a, b) = gcd(b, a mod b)가 성립한다(a mod b = a를 b로 나눈 나머지)
이 등식이 왜 성립하는지는 나중에 설명하고 일단 이 사실을 받아들이자.
큰 문제를 작은 문제로 치환
나머지 a mod b를 c라고 하면 gcd(b, c)라고 할 수 있는데
그러면 여기서 또 gcd(b, c) = gcd(c, b mod c)가 성립한다.
이걸 유클리드 호제법이라고 하는데 이 알고리즘의 핵심은 큰 문제를 작은 문제로 치환하는거다.
48과 18의 최대공약수를 구한다고 해보자. gcd(48, 18)를 구해야 하는 상황이다.
유클리드 호제법에 의하면 gcd(48, 18) = gcd(18, 12)이기 때문에
18과 12의 최대공약수를 구하면 48과 18의 최대공약수를 구하는 것과 같게 된다.
그런데 gcd(18, 12)는 또 유클리드 호제법에 의해 gcd(12, 6)과 같아진다.
12을 6으로 나누면 나머지가 0이 되기 때문에 gcd(12, 6) = 6 이라는걸 알 수 있다.
결과적으로 gcd(48, 18) = gcd(12, 6) = 6, 즉 48과 18의 최대공약수는 6임을 확인할 수 있다.
구현
a mod b가 0이 될 때까지 gcd(a, b) = gcd(b, a mod b)를 반복하면 된다.
def gcd(a, b): while b != 0: a, b = b, a % b
return agcd(12, 6)에 상황에서부터 보자.
gcd(12, 6) = gcd(6, 0), 즉 a = 6, b = 0 이 되는 상황에서 반복문이 멈춘다.
따라서 반복문이 멈춘 후, a값을 반환해주면 두 수의 최대공약수를 얻게 된다.
이때 a와 b의 대소는 상관이 없다.
a = 18, b = 48인 상태로 입력 받아도 gcd(18, 48) = gcd(48, 18 mod 48)이 되는데,
18을 48로 나눈 나머지는 18이기 때문에 결과적으로 gcd(48, 18)가 나온다.
물론 a와 b 대소를 비교해서 큰 값을 a에 넣어주면 반복문을 한번 덜 돌겠지만
대소 비교를 해야하니까 코드가 더 지저분해지고 점근적 시간복잡도에서도 이득이 없다.
gcd(a, b) = gcd(b, a mod b)
아까 말했던 위 등식이 어째서 성립하는지 알아보자.
덧셈 합성으로 표현
a와 b가 주어졌다고 할 때(a > b),
a를 b로 나누어떨어지는 부분과 그렇지 않은 부분의 합으로 나타낼 수 있다.
48과 18로 예를 들면 48을 로 나타낼 수 있다는거다.
a와 b로 일반화해서 쓰면 라고 표현할 수 있다.
동일한 공약수 집합
48과 18의 공약수는 48과 18을 모두 나눌 수 있다.
따라서 18 × 2도 나눌 수 있고, 48에서 18 × 2를 뺀 12도 나눌 수 있다.
즉, 48과 18의 공약수는 18과 12의 공약수이기도 하다.
반대로 18과 12의 공약수는 18 × 2와 12를 더해 만든 48도 나눌 수 있다.
즉, 18과 12의 공약수는 48과 18의 공약수이기도 하다.
그러면 48과 18의 공약수 집합과 18과 12의 공약수 집합은 동일하다는 결론이 나온다.
공약수 집합이 같으니까 그 중에 최대값인 최대공약수도 같다는 사실을 알 수 있다.
그래서 gcd(a, b) = gcd(b, a mod b)라는 수식이 성립하는거다.
직관적 이해
사실 직관적으로는 라는 수식을 보고 바로 이해가 간다.
어떤 수로 a를 나눈 나머지도 0이고 b를 나눈 나머지도 0이면 r을 나눈 나머지도 0이어야 하네
그러면 어떤 수가 a와 b를 동시에 나누어떨어지게 한다는게
b와 r(a mod b)을 동시에 나누어떨어지게 한다는거랑 같은 소리구나
그래서 gcd(a, b) = gcd(b, a mod b) 구나 정도로 이해해도 충분하다.
공부 후기
유클리드 호제법은 복잡하지 않기 때문에 외우는건 어렵지 않은게 아니고
나는 역시 왜 그렇게 되는지 이해를 못하면 외워지지가 않는다..
수학적으로 엄청 엄밀하게 정리한 것도 아니지만 머리 속에서 명쾌해졌다.
이제 최대공약수나 최소공배수 문제가 나오면 죄책감 없이 math 모듈 임포트해서 써야겠다.