최대공약수 최소공배수 알고리즘 : 짧은 코드 이해해 봅시다.

 오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다.

 

 

---

 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다.

 

 

 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 10억 7이 아닌 1밖에 없어요.

 

 즉, 12번째 줄에 걸려서 return 문으로 나가는 경우는 i가 1인 것밖에 없다는 것입니다. 비효율적입니다. 이것을 빠르게 판단할 수 있는 방법이 없을까요?

 

 

---

 a>=b라고 해 봅시다. 그리고 a = bQ + r꼴로 나타내어 질 때, gcd(a,b) = gcd(b,r)이 성립합니다. 이것을 먼저 보여 봅시다. gcd(a,b) = k라고 해 봅시다. 이 말인 즉슨, a와 b를 동시에 나누는 최댓값이 k라는 이야기입니다. 즉, a와 b도 k의 배수라는 것입니다.

 

 

 그러면 a = ka'으로 나타낼 수 있고, b = kb'으로 나타낼 수 있어요. 이 때 gcd(a',b') = 1입니다. 만약에 그렇지 않다면 어떻게 될까요? 그러면, a'과 b'을 동시에 나누는 1보다 큰 자연수 g'이 있다는 겁니다.

 

 

 그러한가요? 네. a'과 b'이 g'로 나누어 진다면, a'/g'과 b'/g' 또한 정수일 거고요. g'이 1보다 크기 때문에 kg'은 k보다 큽니다. 따라서 gcd(a,b)의 값은 kg'보다 크거나 같을 건데, 이 값이 k보다 커져 버리게 됩니다. 따라서 a = ka', b = kb' 꼴로 표현할 수 있을 때, gcd(a',b')의 값은 1입니다. 즉, a'와 b'을 공통으로 나누는 자연수는 1밖에 없습니다.

 

 a = bQ + r꼴로 나타낼 수 있다고 하였습니다. 그러면 gcd(b,r)의 값도 k일까요?

 

 

---

 일단, r이 k의 배수가 아니라고 해 봅시다.

 

 

 그러면 r = kQ' + r' 꼴로 나타낼 수 있을 겁니다. 단, Q'은 정수이고, r'은 0<r'<k인 정수일 겁니다. a = bQ + r 꼴로 나타낼 수 있다고 하였는데요. a = ka', b = kb'으로 나타낼 수 있었습니다. 우변만 적당히 잘 바꿔 보면 kb'Q + kQ' + r'로 나타내어 지는데요. 이것은 k(b'Q + Q') + r'로 나타낼 수 있어요. 그런데 r'이 k로 떨어지지 않아요.

 

 그렇기 때문에 우변이 k로 나누어 떨어지지 않아요. 그런데 a의 값과 우변의 값이 같지 않나요? a는 k의 배수라고 했네요? 모순이에요. 따라서, a를 b로 나눈 나머지인 r 또한 k로 나누어 떨어질 수 밖에 없어요. 그러면, gcd(b,r)의 최대 공약수가 k가 아니라고 해 봅시다. gcd(b,r) = G라고 한다면 G는 당연하게도 k의 배수일 수 밖에 없어요. b와 r은 k로 나누어 떨어지기 때문이에요. 이 G가 k와 같지 않다고 해 봅시다.

 

 

 그러면 이 z는 1보다 큰 정수라는 겁니다. gcd(b,r)이 k가 아니기 때문입니다. a = bQ + r꼴로 나타낼 수 있다고 했습니다. 그대로 대입해 보면, a = (kz...)Q + (kz...)로 나타낼 수 있는데요. kz로 묶여버립니다. 즉 kz(Q... + ...)로 묶이기 때문에, a 또한 kz로 나누어 떨어집니다. b도 kz로 나누어 떨어집니다.

 

 그런데 이는 gcd(a,b) = k라는 전제에 모순이 되어 버립니다. 따라서, b와 r의 최대 공약수 또한 k가 될 수 밖에 없어요. 따라서, a>=b이고, a = bQ + r 꼴로 나타낼 수 있을 때, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같아요.

 

 

 이를 반영한 코드는 다음과 같습니다. a>=b라고 가정했을 때, a가 b로 떨어지면 b를 리턴하고, 그렇지 않다면, b와 a%b의 최대 공약수를 구합니다. 이것을 재귀적으로 표현을 한 것 뿐입니다.

 

 

---

 그러면 a와 b의 최소 공배수 lcm은 어떻게 구할까요? 단, lcm은 0보다 큰 자연수라 합시다. 최소 공배수란 a의 배수이면서, b의 배수인 최솟값을 의미합니다. 이것은 a와 b를 곱한 값에 a와 b의 최대 공약수를 나누면 되는데요. 정의에 충실하면 됩니다. a와 b의 최대 공약수를 k라 하면 a = ka', b = kb'으로 나타낼 수 있고, a'와 b'의 gcd 값은 1입니다.

 

 

 그러면 어떠한 수 T가 a와 b의 배수가 되려면, T는 ka'의 배수여야 하고 kb'의 배수여야 합니다. 이 부분은 부정하지 못할 겁니다. 그러면 T는 다음과 같이 쓸 수 있습니다.

 

 

 

 그런가요? 이 때, ??은 어떠한 정수 값일 거에요. 이렇게 쓰면 T는 ka'로 떨어집니다. ka'로 나누면 몫이 ??이고 나머지는 0이기 때문입니다. 그러면, 이게 kb'으로 나누어 떨어지려면 어떻게 되어야 할까요?

 

 

 그러면 노란색으로 칠한 부분이 b'의 배수가 되어야 합니다. 왜냐하면 gcd(a', b')의 값이 1이기 때문인데요. 공통 소인수를 가지고 있지 않기 때문에, ??가 b'의 배수가 되어야 한다는 것입니다. 0이 아닌 양의 자연수 중에서 b'의 배수인 것들 중 제일 작은 것은 b'입니다.

 

 따라서, a와 b의 최소 공배수는 다음과 같이 쓸 수 있어요.

 

 

 이는 a와 b를 곱한 값인 k^2a'b'에 gcd(a,b)인 k를 나눈 값과 같습니다. 따라서 a와 b의 최대공약수와 a와 b의 최소 공배수를 곱하면 a와 b를 곱한 값과 같습니다.

 

 

 이 정도만 이해하셔도 무난할 듯 싶습니다.