JavaScript 최대공약수(GCD), 최소공배수(LCM) 알고리즘

최대공약수

• 최대공약수는 두개 이상의 자연수의 공약수 중에서 가장 큰 수이다.
• 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나눠보는 방법이 있다.
• 유클리드 알고리즘을 통해 간단한 방법으로 구할 수 있다.

📝  코드

function Gcd(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부터 두 수중 최소값까지 반복문을 돌면서 num1, num2 모두가 나눠지는 수 중 가장 큰 값을 리턴하는데 해당 수가 두 수 num1, num2의 최대공약수가 됩니다.

Math.min 함수는 주어진 숫자들 중 가장 작은 값을 반환합니다.

유클리드 알고리즘(유클리드 호제법)

유클리드 알고리즘은 두 자연수 사이의 최대 공약수를 구하는 알고리즘의 하나이다. 명시적으로 기술된 가장 오래된 알고리즘으로 알려져 있다고 합니다. 원리는 다음과 같습니다.

• 2개의 자연수 a, b에 대해서 큰수를 작은 수로 나눈다.
• 나눈 수의 나머지가 0이라면 작은 수가 최대 공약수다.
• 만약 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눈다.
• 이 과정을 반복하여 나머지가 0이 될 때, 해당 숫자가 두 자연수의 최대공약수다.

📝  코드

function gcd(num1, num2){
	let num = num1 % num2;
  	if(num === 0) return num2;
  	return gcd(num2, num)
}

이론상으로 명시했던 큰 수와 작은 수를 구분하는 코드는 빠져있는데, 그 이유는 어떤 수를 자신보다 더 큰 수로 나누게 되면 몫이 0이 되고 그 자신이 나머지가 되기에 코드에는 빠져있습니다.

함수가 재귀적으로 돌아가면서 마지막 결과값으로는 결국 두 수의 공약수 중 가장 큰 최대공약수를 리턴하게 됩니다.

코드를 좀 더 간결하게 작성하면 다음과 같이 작성이 가능합니다.

function gcd(num1, num2){ 
  return num2 > 0 ? gcd(num2, num1 % num2) : num1;
}

최소공배수

• 최소공배수는 두 개 이상의 자연수의 공배수 중에서 가장 작은 수이다.
• 가장 쉬운 방법은 1부터 시작하여 두 수를 나눈 나머지 값이 0일때까지 1씩 더해가면 된다.
• 두 수의 최대공약수를 구하면 최소공배수를 쉽게 구할 수 있다.

📝  코드

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

두 수의 최대공약수를 유클리드 호제법으로 구해놓으면 쉽게 최소공배수를 구할 수 있습니다.

📝  코드

function gcd(num1, num2){
  return num2 > 0 ? gcd(num2, num1 % num2) : num1;
}

function lcm(num1, num2){
  return num1 * num2 / gcd(num1, num2);
}

응용문제 - 분수의 덧셈 (programmers)

문제 설명

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

두 분수를 더한 값을 기약분수로 나타내려면 더한 값의 분자, 분모를 구해준 뒤 최대공약수로 통분해주면 됩니다.

  📝  코드

// 최대 공약수 알고리즘
function cal_gcd(a, b) {
  return a % b === 0 ? b : cal_gcd(b, a % b);
}

function solution(denum1, num1, denum2, num2) {
  let denum = denum1 * num2 + denum2 * num1;
  let num = num1 * num2;
  let gcd = cal_gcd(denum, num);

  return [denum / gcd, num / gcd];
}