[TIL]9. 최대공약수 최소공배수

알고리즘

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

나는 처음에 어떻게 풀어야할지 몰랐다 그래서 그냥 단순하게 생각해서 두 수가 1,3,5,7로 나누어 떨어지면 나누고 나누다 나누어진 값들을 곱해서 최대공약수를 구했고, 나누어진 몫들까지 다 곱해 최소공배수를 구했다. 근데 큰 오류가 있었다. 소수가 이것들 뿐만은 아니었다. 그러한 경우의 수까지 다 따지기에는 너무 하드했다. 그래서 결국 찾던 와중 유클리드 호제법이란걸 찾았다.

2개의 자연수 n, m(n > m)에 대해서 n을 m으로 나눈 나머지가 r일 때, n과 m의 최대공약수는 m와 r의 최대공약수와 같다.

나머지가 0이 될때까지 나누면 된다는 소리이다.

최소공배수는 더 쉽다. n과 m을 곱한수에 최대공약수를 나누면 최소공배수가 된다.

코드

function solution(n, m) {
    var answer = [];
    var r = 0;
    var a = n * m;         // 최소공배수를 구하기 위한 변수
    while(m != 0){         
        r = n % m;         // n을 m으로 나눈 나머지 r
        n = m;             // r과 m을 나누기 위한 재할당
        m =r;
    }
    answer.push(n)        // 최대공약수
    answer.push(a / n)    // 최소공배수
    return answer;
}

후기

유클리드 호제법을 이해하려 했지만 이해 못할 것 같다. 그냥 그런가보다 하고 이런게 있구나 하고 머리속에 저장해야겠다. 이러한 문제가 나왔을때 호제법을 떠올릴 수 있도록.