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

문제 :

 

 

내 풀이 :

function solution(n, m) {
    let gdc = 1;
    let lcm = 1;
    let gdcAndLcm = [];
    
    for(let i = 2; i <= Math.min(n, m); i++) {
        if(n % i === 0 && m % i === 0) {
            gdc = i;
        }
    }
    
    while(true) {
        if(lcm % n === 0 && lcm % m === 0) {
            break;
        }
        lcm++;
    }
    
    gdcAndLcm.push(gdc, lcm);
    return gdcAndLcm;
}

 

 

최대공약수는 2부터 min(n, m)까지 모든 정수로 나누어보는 방법으로 구했다.

 

각각의 두 수를 lcm으로 나누었을 때 나머지 값이 0인지를 비교하면서 lcm++을 하는 방법으로 구했다.

 

 

다른 사람의 풀이 :

function solution(a, b) {
 	let gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };

    let gcdValue = gcd(a, b);
    let lcmValue = (a * b) / gcdValue;

    return [gcdValue, lcmValue];
}

 

위 풀이는 유클리드 호제법으로 작성한 코드이다.

 

유클리드 호제법의 원리

두 수 a와 b의 최대공약수는 다음과 같은 방식으로 구할 수 있습니다:

1. 큰 수에서 작은 수를 나눈다: 먼저 a를 b로 나누고, 그 나머지를 구합니다. (이때 a > b로 가정합니다.)
2. 나머지가 0이 될 때까지 반복: a와 b를 계속해서 나누되, 이번에는 b를 이전 단계에서 구한 나머지로 나누는 식으로 반복합니다.
3. 나머지가 0이 되는 순간의 나누는 수: 나머지가 0이 되었을 때, 그 직전 단계에서 나누었던 수가 두 수의 최대공약수입니다.

a = 48과 b = 18의 최대공약수

48을 18로 나눈 나머지: 48 % 18 = 12
18을 12로 나눈 나머지: 18 % 12 = 6
12를 6으로 나눈 나머지: 12 % 6 = 0
나머지가 0이 되었으므로, 이때 나누는 수 6이 48과 18의 최대공약수입니다.

 

 

두 수 a와 b의 최소공배수는 두 수의 곱을 그 두 수의 최대공약수로 나누어 구할 수 있습니다.

1. 수학적 성질: 두 수 a와 b에 대해 a * b = GCD(a, b) * LCM(a, b)이 성립합니다.
2. 따라서 LCM(a, b) = (a * b) / GCD(a, b)로 계산할 수 있습니다.

 

유클리드 호제법을 이용하여 문제를 해결하면 큰 수에 대해서도 빠르게 계산할 수 있겠다고 생각했고,

상당히 효율적이라고 느껴졌다.