문제 출처
문제
나의 풀이
무식하게 공약수 중에서 최대, 공배수 중에서 최소로 풀었다...
function solution(n, m) {
let tmp=[];
if (n>m) {
let c=0;
c=n, n=m, m=c;
}
let gcd = lcd = 0;
for (let i=1; i<=m; i++) {
if (m%i===0) tmp.push(i);
}
for (let i=n; i>=1; i--) {
if (n%i===0 && tmp.includes(i)) {
gcd = i;
break;
}
}
let tmp2 = [];
if (gcd===1) {
lcd = n*m;
}
else {
for (let i=1; i<=n; i++) {
tmp2.push(m*i);
}
for (let i=1; i<=m; i++) {
if (tmp2.includes(n*i)) {
lcd = n*i;
break;
}
}
}
return [gcd, lcd];
}
console.log(solution(2,5));최대 공약수의 약수가 공약수이다. 최대 공약수를 알면, 공약수를 쉽게 구할 수 있다. 두 수의 공약수가 1밖에 없을 때 이 두 수를 서로소라고 한다. 공약수가 1밖에 없으니 최대공약수도 1이다.
최대 공약수를 구하는 첫번째 방법
공약수로 나누기
두 수 a,b가 있다고 했을 때 a와 b의 공약수로 두 수를 계속 나눈다. 언제까지? 나누는 수가 1이 아닐 때까지. 나누는 수가 1인 순간, 즉 두 수가 서로소가 되는 순간 그 동안 나눴던 수들을 곱해주면 그게 최대 공약수가 된다. 왜냐면, 최대공약수의 약수가 공약수이므로.
예를 들어, a=60, b=48일 때
60과 48을 2로 나누면, 30과 24가 된다. 또 2로 나누니까 15와 12가 된다. 15와 12의 공약수인 3으로 나누니, 5와 4가 됐다. 5와 4의 공약수가 1밖에 없으므로 끝. 그동안 나눴던 223==12가 최대공약수가 된다.
최대 공약수를 구하는 두번째 방법
지수를 이용하는 방법이다.
지수를 이용하기 위해 소인수 분해를 해야 한다. 소수가 나올 때까지 나누는 게 소인수분해이다. 소인수 분해를 통해 지수 형태로 만들어준다.
60=2^235, 48=2^4*3
이때 최대공약수는 두 수에 공통인 소수 중에서 지수가 더 작은 걸 쓴다.
2^2와 3을 써서 12가 된다.
공배수는 최소공배수의 배수이다.
최소공배수를 구하는 첫번째 방법
최대공약수에 서로소까지 모두 곱하면 된다.
만약 두 수가 아니라 세 수면? 세 개 모두의 공약수를 구할 수 없다면 일단 2개의 공약수 먼저 구해서 걔네끼리 나눠준다. 어떻게든 공약수를 부분적으로 구해서 최종적으로 3개 모두 서로소가 되면 된다.
최소공배수를 구하는 두번째 방법
지수를 이용하는 방법. 두 수에 공통인 소수 중에서 지수가 더 큰 걸 쓰고, 공통이 아닌 소수는 모두 다 쓴다.
유클리드 호제법을 사용한 방법
for loop를 돌면 O(N)이 나오지만, 유클리드 호제법을 사용하면 O(logN)으로 줄일 수 있다.
2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 한다면(단, a>b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r0을 구하고 ,.. 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.gcd(a,b) = gcd(b, a%b) if (a%b == 0) => gcd = b; else gcd (b, a%b)
다른 풀이
0이 나오면 for문 종료
for문이 1이면 계속 나누고, for문이 0이면 종료하면서 a%b==0이라는 의미
function solution(a, b) {
var r;
for(var ab=a*b; r=a%b; a=b, b=r){}
return [b, ab/b];
}
console.log(solution(2,5));while 문으로 반복
const gcd = (a, b) => {
while (b > 0) {
let temp = b;
b = a % b;
a = temp ;
}
// b == 0 이라는 의미는 결굴 a % b == 0이라는 의미니까.
return a;
};
const lcm = (a, b) => {
return (a * b) / gcd(a, b);
};삼항연산자
function solution(n, m) {
let gcd = calc_gcd(n, m);
let lcm = (n * m) / gcd;
function calc_gcd(a, b) {
if (b == 0) return a;
return a > b ? calc_gcd(b, a % b) : calc_gcd(a, b % a);
}
return [gcd, lcm];
}
let input = [2, 5];
console.log(solution(input[0], input[1]));
/*
공약수란, 두 개의 정수가 동시에 나눠지는 수를 말함. 그중 가장 큰 수가 최대공약수임.
큰 수를 작은 수로 나누었을 때 나머지가 0이면 이때 나머지가 최대공약수임. 그러므로 나머지가 0이 될 때까지 나머지로 나누면 됨.
공배수란, 두 개의 정수 모두의 배수가 되는 수를 말함. 두 수를 곱한 다음, 최대공약수로 나눠주면 됨.
이유는?
정수 A = 정수 a * 최대공약수
정수 B = 정수 b * 최대공약수
로 구성되어 있으므로,
최소공배수 = a * b * 최대공약수
두 수의 곱 = a * b * 최대공약수 * 최대공약수
이므로, 이를 최대공약수로 나누면 최소공배수가 도출된다.
*/참고
