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

🐶·2021년 7월 21일

JavaScript algorithm

알고리즘

목록 보기

19/21

최대공약수

최대공약수는 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.
최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어보는 방법이다.

코드

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

최소공배수

두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다.
lcm을 1부터 시작하여 점차 lcm++하면서 각각의 두 수를 lcm으로 나누었을 때 나머지 값이 0인지를 비교한다.

코드

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

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

유클리드 호제법의 기본 원리는 num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다.

r이 0이라면, 그 때의 num2가 최대공약수이다.

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))이 불러지게 된다.

재귀로 접근하지 않는다면 아래와 같이 구현된다. 시간복잡도는O(logN)이 나온다.

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

    return num1;
}

최소공배수는 위에서 구했던 GCD(최대 공약수)를 응용해서 구할 수 있다.
두 수 num1, num2의 최대공약수를 gcd라고 했을 때, 최소공배수 lcm = 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)];
}

응용문제

문제

팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.

출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.
출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다.
여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.

output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.

[빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]

output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.

수도코드

//M과 N의 약수로 직원수가 포함되는지?..
//리턴값의 형태는 [공약수, M/공약수, N/공약수]

//따라서 공약수를 모두 구하여 (반복문 이용)
 //어떤 수(= i)가 1부터 시작하여 1씩 증가, M과 N을 i로 나누었을 때 나머지가 0 인 i만을 추출하면 그게 바로 공약수가 된다
 //그런데 i를 1부터 시작하여 어디까지 반복할 지가 중요하다(시간복잡도 고려)
 //M과 N의 최대공약수의 약수들이 M과 N의 공약수들과 같은 점을 착안하여
  //M과 N의 최대공약수의 제곱근까지만 반복하고(왼편만)
  //(오른편의 경우) M과 N의 최대공약수의 제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.


//이 공약수 기준으로 배열을 오름차순 정리를 해주면 된다

코드로 나타내보면

function divideChocolateStick(M, N) {
  // TODO: 여기에 코드를 작성합니다.

  //M과 N의 약수로 직원수가 포함되는지?..
  //리턴값의 형태는 [공약수, M/공약수, N/공약수]
  let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);
  let gcd = getGCD(M, N)
  let result = [];
  for(let i=1; i<=Math.sqrt(gcd); i++){// 최대공약수까지만 반복해도 됨. 어차피 공약수는 최대공약수 내에서 나올테니까... 그런데 최대공약수의 제곱근까지만 반복하고(좌측만 반복)
      if(gcd % i === 0){ 
        result.push([i, M / i, N / i]) //여긴 좌측
        if(i*i<gcd){ //우측
          let right = (gcd/i)
          result.push([(gcd/i), M/(gcd/i), N/(gcd/i)])
        }
      }
  }
  result.sort((a, b) => a[0] - b[0]); //배열안에 배열의 0번째 요소를 기준으로 오름차순 정렬~

  return result;
}