[JavaScript Algorithm] 최대공약수(GCD), 최소공배수(LCM) - DAY 1

✅ 최대공약수

두 수 A와 B의 공통된 약수 중에 가장 큰 정수

🧐 최대공약수를 구하는 가장 쉬운 방법?
2부터 Math.min(num1, num2)까지 모든 정수로 나누기!

코드

let getGCD = (num1, num2) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }

    return gcd;
}

✅ 최소공배수

2개 이상의 여러 수의 공통인 배수 중 가장 작은 수

🧐 최대공약수를 구하는 가장 쉬운 방법?
lcm을 1부터 증가시키면서 각각의 수를 lcm으로 나누었을 때 나머지가 0인지 비교

코드

let getLCM = (num1, num2) =>{
	let lcm = 1;

    while(true){
      if((lcm % num1 == 0) && (lcm % num2 == 0)) break;
      lcm++;
    }
  
  	return lcm
}

💡유클리드 호제법을 이용한 구현

유클리드 호제법?

• a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)
• 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다
• 서로가 나누어지면 a%b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.

num1을 num2로 나눈 나머지를 r이라고 할 때
GCD(num1, num2) === GCD(num2, r)이고,
r이 0이 될 때 num2가 최대공약수!

ex) num1=24, num2=16
GCD(24, 16) = GCD(16, 8) = GCD(8, 0)
∴ GCD = 8

let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

🧐 만약 num1 < num2 ?
값이 자동으로 정렬된다.

ex) num1=16, num2=24
getGCD(24, (16%24=16))

🧐 recursion말고 while문으로 구현하면 ?
시간복잡도 O(logN)

let getGCD_v2 = (num1, num2) => {

    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    }

    return num1;
}

📌 최소공배수는 GCD(최대 공약수)를 응용해서 구현 가능!
두 수 num1, num2의 최대공약수를 gcd라고 할 때,
최소공배수 = gcd * (num1/gcd) * (num2/gcd)

• num1 * num2 = gcd * lcm 과 같다는 원리를 이용
• lcm = (num1*num2) / gcd 이다.

📝 유클리드 호제법 정리

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(num1, num2), lcm(num1, num2)];
}

❓응용문제 (분수의 덧셈)

코딩테스트 연습 - 분수의 덧셈

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

---

제한사항

• 0 <denum1, num1, denum2, num2 < 1,000

---

입출력 예

denum1	num1	denum2	num2	result
1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

입출력 예 #1

• 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2

• 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

function solution(denum1, num1, denum2, num2) {
    
    let deno = (denum1*num2)+(denum2*num1);
    let numer = (num1*num2);
    
//풀이1 
    // let gcd=1;
    // for(let i=2; i<=Math.min(deno, numer); i++){
    //     if(deno % i === 0 && numer % i === 0){
    //         gcd = i;
    //     }
    // }

//풀이2 유클리드 호제법 응용
    let getGCD = (num1, num2) => (num2>0 ? getGCD(num2, num1%num2) : num1);
    let gcd = getGCD(deno,numer);
    
    return [deno/gcd,numer/gcd];
}

---

📍 Reference

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기