유클리드 호제법이란?
유클리드 호제법은 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.라는 성질을 활용하여 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 방법이다.
•
호제법이란 두 수가 서로를 나누어서 원하는 수를 얻는 알고리즘이다.
최대 공약수 구하기
•
a와 b를 나눈 나머지를 r이라고 하자. (a >= b, 0 <= r < b)
•
이 때 a와 b의 최대 공약수를 (a, b)라고 한다면 다음이 성립한다.
•
(a, b) = (b, r)
•
이후 나머지가 0이 될 때까지 위 방법을 반복하면 최대 공약수를 구할 수 있다.
// JavaScript
// 유클리드 호제법
function findGcd(a, b) {
const remainder = a % b
if (remainder === 0)
return b
return findGcd(b, remainder);
}
// 일반적인 방법
function findGcd(a, b) {
let gcd = 1;
for (let i = 2; i <= Math.min(a, b); i++)
{
if (a % i === 0 && b % i === 0)
gcd = i;
}
return (gcd);
}
JavaScript
복사
•
유클리드 호제법의 경우 나머지(remainder)가 0이 될때까지 재귀로 동작한다.
•
일반적인 방법은 2부터 시작하여 min(a, b)까지 모든 정수로 두 수를 나누는 방법이 있다. 하지만 모든 정수를 나눠야하기때문에 시간 복잡도는 0(N)이 된다. 반면에 유클리드 호제법의 경우 O(logN)의 시간 복잡도를 가진다.
최소 공배수 구하기
// JavaScript
// 유클리드 호제법
let lcm = (a * b) / findGcd(a, b);
// 일반적인 방법
function findLcm(a, b) {
let lcm = 1
while (42)
{
if (lcm % a === 0 && lcm % b === 0)
break ;
lcm++;
}
return lcm;
}
JavaScript
복사
•
LCM을 구하는 일반적인 방법은 두 수로 나눠지는 수를 찾을 때까지 모든 정수에 대해 나눠보는 방법이 있다.
•
a, b에 대해서 최소 공배수와 최대 공약수는 a * b === GCD * LCM 관계가 성립한다.
•
따라서, 최소 공배수는 a * b / GCD를 사용해 구할 수 있다.
예시 문제
•
두 수를 입력받아 두 수의 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM)를 담은 배열을 반환하는 함수를 만드는 문제를 통해 유클리드 호제법을 직접 실습해볼 수 있다.
function findGcd(a, b) {
const remainder = a % b
if (remainder === 0)
return b
return findGcd(b, remainder);
}
function solution(a, b) {
let answer = [];
let gcd = findGcd(a, b);
let lcm = (a * b) / gcd;
answer.push(gcd);
answer.push(lcm);
return answer;
}
JavaScript
복사
