코딩 테스트에서 최대공약수(GCD), 최소공배수(LCM) 유클리드 알고리즘으로 구하기

코딩 테스트를 풀다 보면 의외로 최대 공약수, 최소 공배수를 구해야 할 일이 많습니다.

직접적으로 최대 공약수 / 최소 공배수를 구하라고 하는 문제도 있지만, 아래의 문제는 모두 간접적으로 최대 공약수 / 최소 공배수를 구해 푸는 문제들입니다.

 

• 기약 분수로 만들기
• n개로 나눌때 모든 사람이 같은 개수를 가질 수 있게 하기

---

무식하게 최대 공약수 구해보기

1. 두 수의 약수를 모두 구한다
2. 공통된 약수만 남긴다
3. 거기서 가장 큰 수가 최대 공약수!

---

최소 공배수는 최대 공약수만 구하면 자동으로

최소 공배수의 의미가 뭘까요? x, y의 최소 공배수라 하면,

x, y 모두와 나누어 떨어지는 가장 작은 수

 

즉, 만약 아래와 같이 x, y가 이루어져 있다면

x, y의 최소 공배수는 a, b, c 3개의 숫자로 모두 나누어 떨어져야 합니다. 근데, 단순히 두 수를 곱한다고 하면 두 수에 공통으로 있는 b 때문에 최소 공배수는 아니게 됩니다. 굳이 b가 2번 있을 필요는 없기 때문이죠. 

근데 b가 뭔지 아시나요? 두 수 사이의 공통된 최대 부분, 즉 최대 공약수입니다.

 

---

유클리드 알고리즘으로 효율적으로 최대 공약수 구하기

무식하게 최대 공약수를 구하는 방법은 정확성 측면에서는 전혀 문제가 없지만, 성능이 좋지 않습니다. 하지만 다행히 기원전 300년전에 유클리드가 최대 공약수를 구하는 알고리즘을 발명했습니다.

 

원리는 간단합니다.

두 수의 최대 공약수는, 두 수를 최대 공약수 크기의 조각으로 나눌 수 있습니다. 당연히 두 수가 같지 않는 이상 나눠서 나오는 조각의 개수는 다릅니다. 아래의 그림을 참고해 주세요.

여기서 두 수의 나머지(회색 부분)로 더 작은 조각과 회색 부분의 조각의 나머지를 구하는 과정을 반복하면, 나머지가 0이 되는 때가 옵니다. 이 때, 나누어 떨어지는 부분이 최대 공약수입니다.

---

꿀팁 : 최대 공약수를 구하는 함수를 외워두자

내장함수로 최대 공약수를 구할 수 있다면 상관 없지만, 다른 구현할 것도 많은데 유클리드 알고리즘을 그때그때 직접 구현하려 하면 의외로 부담이 됩니다. 그럴 때를 대비해, 유클리드 알고리즘을 구현한 함수를 외워두는게 큰 도움이 됐었습니다.

 

제가 외워둔 Kotlin 버전의 유클리드 알고리즘입니다.

tailrec fun gcd(max: Int, min: Int): Int = if (min == 0) max else gcd(min, max % min)

 

• tailrec은 꼬리 재귀를 최적화 해 주는 키워드입니다. 성능을 향상시킨다고 생각하시면 됩니다.
• Kotlin에서는 함수가 1줄일 경우 중괄호({})와 return을 생략 가능합니다.
• 함수를 사용하실 때 max에 더 큰 숫자, min에 더 작은 숫자를 넣어야 합니다. 여러가지 변수 이름을 사용해 봤지만 max/min이 가장 간편한거 같습니다.
• max % min 부분이 유클리드 알고리즘의 핵심을 담고 있는 부분입니다.

---