유클리드 알고리즘 - 두 수의 최대공약수는?🤨

🚀Intro

치맥의 고장인 맥치마을에서는 매년 치맥축제🍗🍺를 엽니다. 올해는 축제를 위해 치킨 4,500마리🍗와 맥주 7,500잔🍺을 준비했습니다. 이것들을 최대한 많은 사람들에게 남김없이 똑같이 나누어 주려고 할 때, 1️⃣ 최대 몇 명에게 나누어 줄 수 있으며 2️⃣ 한 사람 당 치킨 몇 마리와 맥주 몇 잔을 받을 수 있을까요?

 

문제를 모두 맞추셨나요? 여러분이 이미 알고 계시듯이 1️⃣번 문제의 답은 4,500과 7,500의 '최대 공약수(Greatest Common Divisor)'인 150명입니다. 또한 2️⃣번 문제의 답은 치킨 4,500마리와 맥주 7,500잔을 최대 공약수인 150으로 나눈 3마리와 5잔입니다. (한 사람당 치킨 세 마리🐓🐓🐓와 맥주 5잔🍺🍺🍺🍺🍺이라니... 정말 좋은 축제네요😋)

 

그렇다면 만약 n년 후 치맥축제🍗🍺가 전세계적으로 대박이 나면서 치킨 9,876,543마리🍗와 맥주 3,456,789잔🍺를 준비한다고 할 때, 1️⃣번 문제와 2️⃣번 문제의 답은 각각 무엇일까요?

 

아마 바로 답을 구하긴 어려우실 것 같은데요. 컴퓨터가 대신 구해보게 하는 것 어떨까요?

 

💭최대 공약수 구하기

두 정수 $a,\ b\ (a \gt b)$의 최대 공약수를 $\gcd(a, b)$라고 합시다. $\gcd(a, b)$를 컴퓨터로 어떻게 구할 수 있을까요?

1. Brute-force 🥊

가장 먼저 무식하게 구하는 방법이 있습니다. $\gcd(a, b)$는 1부터 $b$ 중 $a,\ b$ 모두와 나누어 떨어지는 가장 큰 수입니다. 따라서 1부터 $b$까지 차례로 증가하며 $a,\ b$ 모두와 나누어 떨어지는지 확인하면 됩니다.

 

이 알고리즘을 구현한 코드는 아래와 같고 ⏰시간 복잡도는 $O(b)$입니다.

 

2. 공약수의 성질 이용하기

이번에는 우아하게 수학💫을 이용해볼까요?

공약수의 성질 중 하나는 '두 정수 $a,\ b\ (a \gt b)$의 공약수의 집합은 $a - b$와 $b$의 공약수 집합과 같다'는 것입니다. 이 성질은 아래와 같이 간단하게 증명할 수 있습니다.

 

$pf.\\ a,\ b의 공약수\ g가\ 있다고\ 하자.\\그렇다면\ a = a'g, \ b = b'g라고\ 할\ 수\ 있다.\\\ \\이때,\ a-b = (a'-b')g\ 이므로\\ a,\ b의\ 공약수의\ 집합은\ a - b와\ b의\ 공약수의\ 집합과\ 같다.$

 

이 성질을 이용하면 아래와 같은 코드를 구현할 수 있습니다.

 

이때 ⏰시간 복잡도는 $n = a + b$라고 할 때, $O(n)$입니다. 왜냐하면 $\gcd(a, b)$는 최대 $a+b$번 반복하기 때문인데 다음과 같이 증명할 수 있습니다. 간단하게는 최악의 경우 즉, $gcd(a, 1)$일 때 함수가 몇 번 실행되는지 세는 방법도 있습니다.

 

$pf.\\두 \ 정수 \ a,\ b(a\gt b)에\ 대하여\\\gcd(a, b) = \gcd(a-b, b) = \gcd(a', b')라고\ 하자.\\\ \\이때\ 다음와\ 같은\ 관계가\ 성립한다.\\\begin{cases} a' = a-b\\ b' = b \end{cases}\\\ \\그리고\ a'+b' = a \lt a+b\ 이다.\\따라서\ \gcd(a, b)는\ 최대\ a+b번\ 반복한다.$

 

우아하게 수학을 이용했는데 결과는 그렇게 만족스럽지는 않네요...😂

그렇다면 공약수의 다른 성질을 이용해보면 어떨까요?

 

🔢유클리드 알고리즘

유클리드 알고리즘은 역사상 가장 오래된 알고리즘으로 유명하고 아래와 같은 성질을 이용하여 두 수의 최대 공약수를 구합니다.

 

$두\ 정수\ a,\ b\ (a\gt b)에\ 대하여\ \gcd(a,\ b) = \gcd(b,\ a \mod b)이다.$

 

이 성질은 다음과 같이 간단하게 증명할 수 있습니다.

 

$pf.\\r = a\mod b,\ a = b \times t + r\ (t \in Z)라고 \ 하자.\\\ \\Case\ 1.\ d = \gcd(a, b)일때,\ d \mid (b \times t + r)이고\ d \mid b이다.\\따라서,\ d \mid r이다.\ 그러므로,\ \gcd(a, b) = \gcd(b, r)이다.\\\ \\Case\ 2.\ c = \gcd(b, r)일때,\ c \mid b이고\ c \mid r이다.\\따라서,\ c \mid a이다.\ 그러므로,\ \gcd(b, r) = \gcd(a, b)이다.\\\ \\따라서, \gcd(a, b) = \gcd(b, r)이다.$

 

이 성질을 이용하면 아래와 같은 코드로 구현할 수 있습니다.

 

흠... 근데 과연 이 방법이 다른 방법들 보다 빠를까요? 🤔

 

⏰복잡도 분석

알고리즘의 복잡도를 분석하는 여러 방법들이 있습니다. 그 중 간단하게 매 실행마다 줄어든 자료의 크기로 통해 복잡도를 분석하는 방법이 있습니다. 그럼 한 번 분석해볼까요?

 

유클리드 알고리즘은 두 정수 $a,\ b\ (a \gt b)$에 대하여 $b$가 0이 될 때까지 반복적으로 함수를 호출합니다.

그럼 아래와 같이 경우를 나눠서 생각해보는 건 어떨까요?💡

 

$\gcd(a, b) = \gcd(a', b') = \gcd(b, a \mod b)라고\ 할\ 때\\\ \\Case\ 1\ :\ b\ (=a') \gt \frac{a}{2}\\\ \\a \mod b(=b') = a - b \lt \frac{a}{2}\\\ \\Case\ 2\ :\ b(=a') \le \frac{a}{2}\\\ \\a \mod b(=b') \lt b \le \frac{a}{2}$

 

경우를 나눠보니 $a \mod b \lt \frac{a}{2}$인 것이 분명해졌습니다. 그러므로 매 실행마다 자료의 크기가 절반 이상 줄어든다는 사실을 알 수 있습니다. 따라서, ⏰시간 복잡도는 $O(\log(\min(a, b))$입니다.

 

Let's do PS😆

그럼 오늘 공부한 내용들로 문제를 해결해볼까요?

오늘 해결할 문제는 BOJ 2609 - 최대공약수와 최소공배수입니다.

먼저 스스로 해결해보시고 도움이 필요하시면 아래 코드를 참고하세요.

 

Further Thinking🧐

$\gcd(a, b) = d$ 라고 할 때 $d = ax + dy\ (x, y \in Z)$로 정의할 수 있습니다.

왜냐하면 $d$는 $a, b$의 최대 공약수이기 때문입니다. 그렇다면 이때 $x$와 $y$의 값은 어떻게 알 수 있을까요?

그리고 이걸 도대체 어디에 응용할 수 있을까요?

그것들은 다음 강의에서 알아보겠습니다. 👨‍🏫👨‍🏫👨‍🏫

 

📚참고

https://ko.wikipedia.org/wiki/유클리드_호제법

https://book.algospot.com/

https://codility.com/media/train/10-Gcd.pdf