8. 유클리드 호제법

문제해결을 위한 알고리즘 입문

Feb 28. 2025

이번에는 자연수A와 B의 최대공약수를 구하는 문제를 다룹니다. 이전에 다룬 소수판별법과 마찬가지로 단순한 방법으로 계산하면 시간이 오래 걸립니다. 하지만 유클리드 호제법을 사용하면 계산량이 O(log(A+B))로 답을 구할 수 있습니다. 이번에는 알고리즘 소개와 함께 왜 계산량에 로그가 등장하는지도 설명합니다.

(1) 단순한 알고리즘

우선 33과 88의 최대공약수를 계산해 보겠습니다. 답은 명백히 33이하입니다. 따라서 '1, 2, ...., 33 각각에 대해 33과 88모두를 나눌 수 있는지'를 확인하는 방법을 생각할 수 있습니다. 그러나 손으로 일일이 계산하면 답을 찾는데 시간이 많이 소요됩니다.

일반적인 양의 정수 A와 B의 최대공약수 역시 1부터 min(A, B)까지 각각이 두 수 모두를 나눌 수 있는지 확인하여 구할 수 있습니다. 예를 들어, 아래 코드와 같이 구현이 가능합니다. 하지만, 나머지 연산을 2 x min(A, B)번 수행해야 하므로 효율적이지 않습니다.

(2) 효율적인 알고리즘: 유클리드 호제법

사실 다음과 같은 방법을 사용하면 두 수의 최대공약수를 빠르게 계산할 수 있습니다.

큰수를 작은수로 나눈 나머지로 바꾸는 작업을 반복합니다.

한쪽이 0이 되면, 작업을 종료합니다. 남은 수가 최대공약수입니다.

예를 들어, 이 방법으로 33과 88의 최대공약수, 123과 777의 최대공약수를 각각 계산하면, 계산과정은 아래와 같이 진행됩니다. 앞서 설명한 방법과 비교할 때, 계산횟수가 훨씬 적습니다.

이와 같은 알고리즘을 유클리드 호제법이라고 합니다. A와 B의 최대공약수를 구할 때 계산량은 O(log(A+B))이므로, A와 B가 10^18 정도의 크기여도 순식간에 계산할 수 있습니다. 구현한 예시의 코드는 아래와 같습니다. A와 B의 크기 관계에 따라 수행해야 할 작업이 달라지므로, if문을 사용하여 경우를 나누고 있습니다. 또한, 재귀함수를 이용한 효율적인 구현방법도 있습니다.

(3) 유클리드 호제법이 올바르게 동작하는 이유

<이 내용은 난이도가 높아서 건너뛰어도 좋습니다>

유클리드 호제법을 사용하여 올바른 최대공약수 값ㅅ을 구할 수 있는 이유는 한번의 연산으로 두 수의 최대공약수가 변하지 않기 때문입니다. 아래 그림은 33과 88의 최대공약수를 구하는 과정을 보여주며, 최대공약수는 11로 변하지 않습니다.

이것이 항상 성립하는지 확인하기 위해, 여기서는 직사각형을 이용하여 설명합니다. 먼저 '세로A x 가로B인 직사각형에 딱 맞게 채울 수 있는 가장 큰 정사각형의 한변의 길이가 바로 정수 A와 B의 최대공약수'라는 성질이 있습니다. 예를 들어, 33과 88의 최대공약수는 11이므로 33x88의 직사각형은 11x11 정사각형 24개로 채울 수 있습니다.

여기서 한번의 연산은 아래 그림처럼 직사각형에서 몇개의 정사각형을 제거하는 작업에 대응합니다. 예를 들어, 33x88의 직사각형에 대해 연산을 수행하면, 88 ÷ 33 = 2 나머지 22가 되어 33x33 정사각형 2개를 제거하고, 33x22의 직사각형이 남게 됩니다. 즉, (A, B) = (33, 88)인 경우, 한번의 연산후 (33, 22)가 되어 남은 직사각형 크기를 나타냅니다.

이 사실을 이용해 왜 최대공약수가 변하지 않는지를 설명해 보겠습니다.

첫번째, 아래 성질에 의해 연산 후의 최대공약수는 연산 전의 최대공약수 a의 배수가 됨을 알 수 있습니다. (☆)

제거된 정사각형은 한변의 길이가 a인 정사각형으로 채울 수 있습니다.

따라서 연산 후, 남은 직사각형도 한변이 a인 정사각형으로 채울 수 있습니다.

예를 들어, 아래 그림에서 제거된 33x33정사각형은 11x11정사각형으로 채울 수 있습니다. 따라서, 33x88의 직사각형뿐만 아니라, 33x22의 직사각형도 11x11정사각형으로 채울 수 있으므로, 33과 22의 최대공약수는 11의 배수가 됩니다.

두번째, 아래 성질에 의해 연산 전의 최대공약수는 연산 후의 최대공약수의 배수가 됩니다. (★)

연산 후 남은 직사각형의 세로와 가로의 최대공약수를 x라고 합시다.

이때 연산 전의 직사각형도 x x x정사각형으로 채울 수 있습니다.

예를 들어, 33과 22의 최대공약수를 x라고 생각하고, 아래 그림처럼 제거된 정사각형을 추가하면, 33x88의 직사각형도 x x x정사각형으로 채울 수 있게 되어, 33과 88의 최대공약수는 x의 배수가 됩니다.

따라서 ☆와 ★를 모두 만족하기 위해서는 '연산 후의 최대공약수'와 '연산 전의 최대공약수'가 동일해야 합니다. 즉, 한번의 연산으로 두 수의 최대공약수는 변하지 않습니다. 그러므로

처음의 A와 B의 최대공약수

한쪽이 0이 되어 연산이 종료된 시점에서의 A와 B의 최대공약수

가 일치하며, 후자는 명백히 '0이 아닌 다른 한쪽의 수'이므로, A와 B의 최대공약수는 '0이 아닌 다른 한쪽의 수'가 됩니다. 이것이 유클리드 호제법이 올바르게 동작하는 이유입니다.

(4) 계산횟수가 log가 되는 이유

다음으로 계산량이 O(log(A+B))가 되는 이유느를 생각해 보겠습니다. 우선 '한번의 연산으로 A+B의 값이 반드시 2/3배 이하로 줄어든다'는 중요한 사실이 있습니다. 예를 들어, A=33, B=88의 경우 계산과정을 보면, 실제로 값이 2/3배 이하로 줄어듭니다. 이 사실이 왜 성립될까요?