[Algorithm] 최대공약수와 최소공배수

프로그래머스 - 최대공약수와 최소공배수

단순히 최대공약수와 최소공배수를 구하는 문제!

일반적인 코드로 최대 공약수를 구해 본다면 아래와 같이,

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;
}

최소 공배수를 구하는 코드는 아래와 같이,

let getLCM = (num1, num2) =>{
	let lcm = 1;
   
    while(true){
      if((lcm % num1 == 0) && (lcm % num2 == 0)){
        break;
      }
      lcm++;
    }
  	return lcm
}

짜여질 것이다.
이와 같은 최대공약수, 최소공배수를 구하는 코드의 시간복잡도는 단순 O(N)으로 나타난다.

BUT,

이를 더 효율적인 시간복잡도 O(logN)을 지닌 코드로 구현하는 방법이 있는데 이는 바로, '유클리드 호제법' 을 이용한 것이다.

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

• a를 b로 나눈 나머지를 r이라고 할때 (단, a > b) a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 성질을 이용
• 순서쌍의 곱이 0이 될 때 까지 풀이를 진행

참고 - devLulu님 블로그