문제설명📖
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한사항🔐
- 두 수는 1이상 1000000이하의 자연수입니다.
코드🔑
function solution(n, m) {
let minN = [];
let minM = [];
let min = [];
let max = 0;
for(let i = 1 ; i <= n ; i++){
if(n%i == 0) minN.push(i);
}
for(let i = 1 ; i <= m ; i++){
if(m%i == 0) minM.push(i)
}
for(let i = 0 ; i < minN.length ; i++){
for(let j = 0 ; j < minM.length; j++){
if(minN[i] == minM[j]) min.push(minN[i])
}
}
let bigNum = n>m?n:m;
let bigN = [];
let bigM = [];
let i = 1;
while(i<=bigNum){
bigN.push(i*n);
bigM.push(i*m);
i++;
}
let big = [];
for(let i = 0 ; i < bigN.length ; i++){
for(let j = 0 ; j < bigM.length ; j++){
if(bigN[i] == bigM[j]) big.push(bigN[i])
}
}
return [min.pop(),big[0]];
}저는 그냥 최소공배수 / 최대 공약수 를 구할 수 있는 정석으로 구했지만
가급적 제 방법은 따라하시지 않음이.....
- 최대공약수
- 주어진 두 수의 모든 약수를 구함
- 모든 약수를 배열에 집어넣음
- 해당 배열에서 가장 마지막 수를 가지고 옴.
- 최소공배수
- 주어진 두개의 수 중 가장 큰수만큼 반복
- i랑 주어진 수를 곱해 배열에 push
- 두개의 배열을 돌아가며 같은수가 존재하면 또 배열에 push
- 해당 배열의 맨 처음값을 가지고 옴.
다른사람들의 풀이📚
function gcdlcm(a, b) {
var r;
for(var ab= a*b;r = a % b;a = b, b = r){}
return [b, ab/b];
}정말 해당 코드보고 ㅇㅅㅇ..? ㅇㅅㅇ..? 댓글도 다들
이런 반응이더라구요.... 너무 충격받아 코드를 뜯어보던 와중 '유클리드 호제법' 이라는걸 배웠고 이걸 먼저 설명하고 코드를 분석해보려고합니다.
유클리드 호제법
유클리드 호제법은 최대공약수(GCD)를 구할때 자주 사용되는 알고리즘이며 꽤 오래된 알고리즘이다.
❓ 호제법이란
두 수가 상대방 수를 나누어 원하는 알고리즘을 얻음
예시)
2개의 자연수 a, b에 대해 a % b == r 이면 a,b 최대공약수는 b 와 r 의 최대공약수와 같다.
→ 해당 성질에 따라 b % r == r' 을 구하고 r % r' 로 나눈 나머지를 반복하면 나머지가 0이 되는 그순간이 최대공약수이다.
코드 풀이
for(시작하는 수 ; 조건식 ; 증감식)즉 주어진 a,b의 수를 곱한 수부터 시작한다 호제법에서 설명한 것처럼 계속해서 반복해서 r = 0 이되면 반복문을 빠져나가도록 조건식을 만들었다.
증감식에서는 b % r 식을 이용해서 사용해야하므로 a는 b로 바꿔주고 b는 r로 바꾸어서 b % r 식이 성립하게 값을 바꾸어준다. → 이렇게 하면 최대공약수가 나온다.
최소공배수는 두개의 값의 곱 / 최대공약수
이렇게 두개의 값을 구할 수 있다.
⭐ 기억하자 유클리드 호제법 ⭐
