문제
풀이
최대공약수와 최소공배수를 구하는 문제는 코딩테스트에 종종 등장하는 것 같습니다.
손으로 구하는 방법은 다음과 같습니다.
코드로 구현하면 보통은 유클리드 호제법이란 것을 많이 씁니다만, 차근차근 어떤 방법이 있는지 알아봅시다.
각 방법에 대한 설명은 https://m.blog.naver.com/okkam76/221306562506 여기 자세히 나와있으나, 파이썬 코드를 기준으로 하니 참고해주세요.
최대공약수 구하는 방법(기본)
function gcd(a, b) {
let init = 1;
for(let k=2; k<=Math.min(a, b); k++){
while((a % k == 0) && (b % k == 0)) {
a = Math.floor(a / k); // 약수 찾았으면 약수로 나누기
b = Math.floor(b / k);
init = init * k; // 모든 찾아진 약수의 곱이 최대공약수가 됨
continue;
}
}
return init;
}위의 방법을 간단히 설명하면 2부터 파라미터로 들어온 두 수중 작은 수에 도달할 때까지 k값을 증가시켜 최대 공약수를 얻어내는 방법입니다.
a = 60, b = 48 의 수를 받았다고 예를 들면, k가 2부터 두 수중 작은 수인 48에 도달할 때까지 1씩 커집니다.
k는 총 min-1 즉, 최악의 경우에는 47번의 반복을 합니다. 만일, a가 k로 나누어 떨어지며, b가 k로 나누어 떨어지면, 최소 공약수가 아니라도 일단은 공약수를 찾은 것입니다.
루프별로 값을 적어보며 이해해본다면 첫 루프 때 a=60, b=48, k=2의 값이 들어갑니다.
처음부터 60 % 2 == 0, 48 % 2 == 0이 성립하기 때문에 while 내부의 조건이 일치합니다.
그래서 while 루프 안에 들어가게 됩니다. 이후에 while 루프 안에서 a = Math.floor(a / k)를 수행하게 되어, a는 30이 되고, 그 이후에는 b = Math.floor(b / k)를 수행하게 되어, b는 24가 됩니다. 그리고 init에는 2가 들어가게 됩니다.
a=30, b=24는 또 한번 while 루프의 조건을 만족하게 되고, a는 15, b는 12가 됩니다. 그리고 init에는 4가 들어가게 됩니다. 이후에는 k의 값인 2로는 나누어 떨어지지 않게 됩니다.
다음은 k가 3이 되고, a는 5 b는 4가 됩니다. 그리고 init에는 12가 들어갑니다. 이후에는 만족하는 k가 생기지 않아서 더 이상 while 루프에 들어가지 않게 됩니다.
이제 init에 있는 수는 최대공약수가 됩니다.
결국 서로소가 나올때까지 양쪽 수에 공약수를 나누고, 나온 공약수를 전부 곱하면 최대공약수가 나옵니다.
최소공배수 구하는 방법(기본)
공배수 중 가장 작은 공배수가 최소공배수입니다. 이를테면 2와 3의 공배수는 6, 12, 18, ... 등이 있겠죠. 그러면 가장 작은 수는 6이기 때문에 최소공배수는 6입니다.
최소공배수를 구하는 방법은 아주 쉽습니다. 이전에 최대공약수를 구했던 것에서 시작하면 최대공약수 * 서로소 둘 을 하면 됩니다. 이를테면 아까 60과 48의 경우 12가 최대공약수였고 남은 서로소가 5와 4였으니 12 * 5 * 4를 하면 240이 최소공배수가 됩니다.
기본적인 방법을 이용한 정답코드
function gcdAndLcm(a, b) {
let gcd = 1;
for(let k=2; k<=Math.min(a, b); k++){
while((a % k == 0) && (b % k == 0)) {
a = Math.floor(a / k); // 약수 찾았으면 약수로 나누기
b = Math.floor(b / k);
gcd = gcd * k; // 모든 찾아진 약수의 곱이 최대공약수가 됨
continue;
}
}
let lcm = a * b * gcd;
return [gcd, lcm];
}유클리드 호제법은 추후에 수정 업데이트 하겠습니다.
