1. 최대공약수와 최소공배수
최대공약수(GCD, Greateast Common Division)는 두 수에 대한 공약수의 최대값을 의미하고, 최소공배수(LCM, Least Common Multiple)는 두 수에 대한 공배수의 최소값을 의미합니다.
최대공약수와 최소공배수는 소인수분해(Integer factorization)를 통해 구할 수 있습니다.
최대공약수는 소인수의 교집합을 모두 곱한 값이고, 최소공배수는 소인수의 합집합을 모두 곱한 값입니다. 예를 들어 a = 12, b = 20 인 경우, a와 b의 최대공약수와 최소공배수는 다음과 같이 구할 수 있습니다.
a = 12 = 2 * 2 * 3 b = 20 = 2 * 2 * 5
a와 b의 소인수에 대한 교집합은 [2, 2]가 되고, 이를 모두 곱한 4가 최대공약수가 됩니다. 또한 a와 b의 소인수에 대한 합집합은 [2, 2, 3, 5]가 되고, 이를 모두 곱한 60이 최소공배수가 됩니다.
최대공약수를 G, 최소공배수를 L이라고 한다면, 다음과 같은 식이 성립합니다.
a = 12 = G * A b = 20 = G * B
A = a/G
B = b/G
L = G * A * B = G * (a/G) * (b/G) = a*b/G |
이때 A와 B는 서로소가 됩니다.
이를 자바스크립트 코드로 나타내면 다음과 같습니다.
function GCD(a, b) {
let result = 1;
if(a > b) [a, b] = [b, a];
let i = 2; while(1) { while(a%i === 0 && b%i === 0) { a /= i; b /= i; result *= i; } if(a === 1 || a === i++) return result; } }
function LCM(a, b) { return a * b / GCD(a, b); } |
2. 유클리드 호제법(Euclidean algorithm)
두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)이다. r = 0이라면, a, b의 최대공약수는 b가 된다.
유클리드 호제법(Euclidean algorithm)은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법입니다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 합니다.
소인수 분해를 통해 최대공약수를 구하면 시간 복잡도가 O(N) 이지만, 유클리드 호제법으로 최대공약수를 구하면 시간 복잡도를 O(logN)으로 줄일 수 있습니다.
유클리드 호제법의 증명은 다음과 같습니다.
- gcd(a, b) = G, gcd(b, r) = G'라고 가정 한다면, 서로소인 두 정수 A, B에 대하여 a = GA, b = GB가 성립합니다.
- a = bq + r 식에 b를 대입하면 GA = GBq + r 가 되므로 r를 좌변으로 하여 정리하면 r = G(A - Bq) 가 됩니다. 여기에서 G는 b와 r의 공약수임을 알 수 있으며, 그러므로 G는 G'의 약수임을 알 수 있습니다.
- G' = mG 라고 가정한다면, 서로소인 두 정수 k, l에 대하여 b = GB = G'k = Gmk, r = G(A - Bq) = G'l = Gml 이 성립합니다. 양변을 G로 나누면 B = mk, A - Bq = ml 이 성립합니다.
- 두 연립방정식으로부터 A = ml + Bq = ml + mkq = m(l + kq) 가 되므로, m은 A와 B의 공약수가 됩니다. A와 B는 서로소 관계에 있으므로, m = 1 이 되며, G` = G 가 됩니다. 즉, gcd(a, b) = gcd(b, r) 입니다.
- r = 0 인 경우, a = bq 가 되므로, b가 최대공약수가 됩니다.
3. 소스 코드
자바스크립트를 통해 유클리드 호제법을 나타내면 다음과 같습니다.
function GCD(a, b) { return b ? GCD(b, a % b) : a); }
function LCM(a, b) { return a * b / GCD(a, b); } |
a보다 b가 크면 a와 b의 위치를 바꿔서 알고리즘을 수행합니다. 유클리드 호제법에 따라 gcd(a, b) = gcd(b, r) 이고 r = 0인 경우 b가 최대공약수가 되므로 r = 0 이 될때까지 gcd 함수를 재귀 호출하여 a를 리턴 받으면 최대공약수가 됩니다. (재귀 호출의 마지막에 매개변수 a에는 b가 들어갑니다.)
최소공배수의 경우 a * b / gcd(a, b) 이므로 해당값을 리턴하면 됩니다. |
스팟 
