[js] 최대공약수와 최소공배수_Maximum common divisor Minimum common multiple_Gcd And Lcm

[문제 설명]

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

 

[제한 사항]

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

 

[입출력 예]

nmreturn

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

 

[입출력 예 설명]

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

 

 

[문제 풀이]

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

 

 

 

[해설]

유클리드 호제법을 활용했습니다.

우선 gcd는 최대공약수를 구하는 함수로, 재귀 함수를 이용하였습니다.

재귀 함수를 이용하지 않는다면 다음과 같이 구현할 수 있습니다.

let gcd = (a, b) => {
        while(b > 0){
        let r = a % b;
        a = b;
        b = r;
    };

 

lcm(최소공약수)는 두 숫자의 곱을 최대공약수로 나눈 값과 같다는 것을 이용했습니다.

문제에서 리스트로 반환하라는 얘기 없이 대괄호 안에 최대공약수와 최소공약수를 차례로 반환하면 되므로 [gcd 값, lcm값] 으로 반환하였습니다.

 

 

 

*유클리드 호제법

숫자 a와 b가 있을 때, a를 b로 나눈 나머지는 r이라고 가정합니다.

이때 gcd(a,b) = gcd(b,r)이라는 것이 유클리드 호제법의 기본 원리입니다.

 

즉, 만약 r == 0 이라면 b가 최대 공약수, 아니라면 a에는 b 값을, b에는 a%b 값을 넣어주어 반복하면 됩니다.

 

 

 

 

[다른 사람 풀이 1]

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

 

 

마찬가지로 유클리드 호제법을 활용, for문을 이용하여 구현한 코드입니다.

기본적으로 많이 사용되는 for문은 아래와 같아서 저처럼 처음 코드를 보고 오잉?하셨을 분들을 위해 해석을 조금 적어봅니다. 필요하신 분들은 접은 글을 참고해주세요.

• 많이 사용되는 for문

let str = '';

for (let i = 0; i < 9; i++) {
  str = str + i;
}

 

• for문 구문

for ([initialization]; [condition]; [final-expression])
       statement

- initialization : 변수/식 선언. var 키워드로 선언 시, 반복문에 제한 X. let 키워드로 선언 시, 변수는 반복문의 지역 변수가 됨.

- condition : 매 반복마다 평가할 식. 결과가 참이라면 statement 실행. 이 식을 넣지 않으면 언제나 참. 거짓이라면 for문의 다음 식으로 건너 뜀.

- final-expression : 매 반복 후 평가할 식. 다음 condition 평가 이전에 발생.

- statement : 조건의 결과가 참일 때 실행.

위 식에서는 우선 r 값을 선언합니다.

그리고 만약 r이 a%b 즉, b가 0이 아니라면(참) : a에 b를, b에 r을 넣어 반복합니다.

r이 a%b가 아니라면 즉, b가 0이라면(거짓) : for문을 나와 최대공약수인 b와 최소공배수인 ab/b의 값을 반환합니다.

 

 

 

 

[다른 사람 풀이 2]

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

제가 짠 코드와 거의 동일하지만 gcd 함수를 더 간결하게 표현하였습니다.

다른 부분을 비교하자면 아래와 같습니다. 

/* 제가 푼 방식 */
let gcd = (a, b) => {
        if (b==0) return a;
        return gcd(b, a%b);
    };

/* 이 풀이 방식 */
const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);

 

 

 

[다른 사람 풀이 3]

function greatestCommonDivisor(a, b) {return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);}
function leastCommonMultipleOfTwo(a, b) {return (a * b) / greatestCommonDivisor(a, b);}
function gcdlcm(a, b) {
    return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)];
}

최대공약수와 최소공배수를 각각 함수로 구현한 코드입니다.

 

 

 

 

[느낀점]

이 문제를 풀면서 사실 재귀함수로 구현하는 것이 오래 걸렸습니다. 지금까지 푼 문제에서는 재귀함수를 쓸 일이 없어서 그랬던 것 같습니다. 재귀함수의 쓰임에 대해 공부할 수 있었습니다.

 

그리고 for문에 대해 정확하게 이해할 수 있었습니다. 사실 for문은 자주 쓰이는 형태로만 쓸 수 있다고 생각하고 그런 식으로만 구현해왔었는데, 이번 문제를 풀고 다른 분의 풀이를 보면서 for문의 쓰임과 또 다른 구현 방식에 대해 인지하였습니다. 다음에 기회가 된다면 꼭 이러한 방식으로 for문을 구현해보고 싶습니다.

 

위에 있는 여러 코드들 중 가장 효율이 좋은 코드를 알아보고, 어떤 경우에 어떤 방식을 사용하는 것이 좋은지에 대해 고민해보아야겠습니다.

 

 

 

 

[github] - GcdAndLcm.js

https://github.com/yh725k/javascript.git

GitHub - yh725k/javascript