Javascript 최대공약수와 최소공배수

Javascript 치대공약수와 최소공배수

 

 

문제 : 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

n / m / return

3	12	[3, 12]
2	5	[1, 10]

주어진 코드 ↓

function solution(n, m) {
    var answer = [];
    return answer;
}

---

중학교 교육과정을 마친지가 너무 오래되어

최대공약수 찾는 방법과 최소공배수 찾는 방법을 따로 찾아보았다.

그 과정에서 알고리즘 대 선배인 유클리드 선배의 유클리드 호제법을 보고서

감탄할 수 밖에 없었다. 무려 기원전 300년전, 그러니까 지금으로부터 2320년 전에 

유클리드 선배가 작성한, 가장 오래된 알고리즘이라고 한다.

가슴이 웅장해질 수 밖에 없다. 

유클리드 선배께 꾸벅 인사를 박고 시작하겠습니다. 

 

최대공약수 구하기

일단 최대공약수가 무엇인지 알기 위해서는 공약수가 무엇인지 알아야 한다.

공약수란 두 개의 정수가 동시에 나누어지는 수를 말한다.

 

예를 들어서 8과 12의 두 수가 있을 때 약수는 1, 2, 4의 공약수가 있는데,

이때 최대공약수는 가장 큰 4를 의미한다. 

 

이것을 유클리드 선배는 어떻게 푸셨냐면,

큰수를 작은 수로 나누었을 때 나머지가 0 이면, 작은 수가 최대공약수라는 것이다.

그런데, 만약에 나머지가 0이 아니라면,

나눈 작은 수를 나머지로 나누어 나머지가 0 이면, 이 때 나머지가 최대공약수라는 것이다.

그러니까 나머지가 0이 될 때까지 나머지로 나누면 된다.

이 부분에서 재귀를 활용하면 될 것 같았다.

 

최소공배수 구하기

반대로 최소공배수를 알기 위해서는 공배수가 무엇인지 알아야 한다.

공배수란 두 개의 정수 모두의 배수가 되는 수를 말한다.

 

예를 들어서 72과 192의 배수는 72, 144, 192, 216, 288, 360, 384  .. 등이 된다. 

이때 최소공배수는 576 이다.

단순히 두 수를 곱하면 되지 않을까 싶지만,

위의 예시처럼 그렇지 않고, 두 정수의 값이 크면 파악하기가 쉽지 않아진다. 

하지만, 최대공약수를 안다면 쉽게 구할 수 있다.

두 수를 곱한다음 / 최대공약수로 나누어 주면 된다.

 

왜 그렇냐면,

A라는 정수는 a라는 약수 x 최대공약수 로 이루어져 있다.

B라는 정수도 b라는 약수 x 최대공약수로 이루어져 있다.

a x b x 최대공약수 로 구성된 것이 최소의 공배수가 되는 것이다.

 

예를 보자.

72와 192의 최대공약수는 24이다.

72 = 3 * 24 로 이루어져 있고,

192 = 8 * 24 로 이루어져 있다. 

이 때 3과 8이 서로 나누어지지 않는 공약수가 1뿐인 서로소다. 

그리고 공통의 최대공약수로 구성되어 있으니,

이들만 곱했을 때가 최소의 공배수가 나온다.

3 x 8 x 24 = 576.

 

싱글벙글한 수학의 세계다. 

 

function solution(n, m) {
    let answer = [];
    let biggerNumb = 0;
    let smallerNumb = 0;
    
    if(n > m){
        biggerNumb = n;
        smallerNumb = m;
    }else{
        biggerNumb = m;
        smallerNumb = n;
    }
    
    function recursion(biggerNumb, smallerNumb){
        if(biggerNumb % smallerNumb === 0){
            return answer.push(smallerNumb);
        }else{
            recursion(smallerNumb, biggerNumb % smallerNumb);
        }
    }
    recursion(biggerNumb, smallerNumb);
    answer.push(biggerNumb * smallerNumb / answer[0]);
    
    return answer;
}

우선 어느 수가 큰지 작은지 판단하기 위해서

if 문으로 할당해 준 다음,

 

재귀 함수를 만들어서 나머지가 0일때까지 

계속해서 나머지로 작은 수를 나누어주도록 작성했다.

 

그렇게 나온 값을 array.push() 메서드를 이용해서

순서대로 담아줬다.

 

여기까지가 제 풀이방법이고,

다른 풀이법을 찾아보았습니다.

 

function gcdlcm(a, b) {
  var gcd = calc_gcd(a, b);
  var lcm = (a * b) / gcd;

    return [gcd, lcm];
}

function calc_gcd(a, b) {
  if (b == 0) return a;
    return a > b ? calc_gcd(b, a % b) : calc_gcd(a, b % a);
}

제가 푼 방식과 크게 다르지 않은데 훨씬 간결한 방법입니다.

큰 함수에서 최대공약수와 최소공배수를 정의하고,

최대공약수를 구하는 식을 재귀적으로 풀어냈는데 삼항연산자를 활용했습니다.

return 에 삼항연산자를 넣으면서 자신의 함수를 호출하는 방식으로

재귀를 구현할 수 있다는 것을 알게됐습니다!

 

재귀함수도 삼항연산자로 간단하게 구현해보자!

 

 

 

 

 

Javascript 치대공약수와 최소공배수