최대공약수
두 수가 주어졌을 때, 두 수의 공통된 약수 중 가장 큰 것을 최대공약수라고 한다.
학창시절 1부터 두 수 중 작은 수까지 두 수를 각각 나누었을 때 나누어 떨어지는 수 중 가장 큰 것을 찾는 방식으로 최대공약수를 구하곤 했다.
function gcd(a, b) {
__let g = 0;
__for (let i=1; i<=Math.min(a, b); i++)
____if (a%i == 0 && b%i == 0)
__g = i;
__return g;
}
하지만, 알고리즘 문제를 풀면서 위의 방식으로 하면 이중반복문을 쓰면서 주어진 수가 많이 주어지면 실행시간이 길어지는 문제가 발생했다.
이를 해결하기 위해 ‘유클리드 호제법’이라는 것을 사용했다.
유클리드 호제법
유클리드 호제법은 고대 그리스 수학자 유클리드가 두 수의 최대공약수를 구하는 공식을 정의한 것이다.
두 양의 정수 a, b(a>b)에 대하여 a = b * q + r (0≤r<b) 이라 하면,
a와 b의 최대공약수는 b와 r(a를 b로 나눈 나머지)의 최대공약수와 같다.
즉,
__GCD(a, b)=GCD(b, r)
___* r=0이라면, a,b의 최대공약수는 b가 된다.
자세한 증명은 여기를 참고하자.
정리하자면, 숫자 A와 B가 있을 때(A>B), 이 둘의 최대공약수(GCD)는 A%B(A를 B로 나눈 나머지)와 B의 최대공약수와 같다.
이것을 JavaScript 재귀함수로 표현하면 다음과 같다.
function gcd(a, b) {
__if(b==0) {
___return a;
__}
__return gcd(b,a%b);
}
최대공약수 구하는 함수를 활용하여 최대공배수를 수식으로 표현하면 다음과 같다.
L = A * B / G
function lcm(a, b) {
__return a*b/gcd(a,b);
}
… 작성중 …
0 를 눌러주세요! 행복해져요!