알고리즘 - 최대공약수와 최소공배수

프로그래머스 레벨1 문제 중에 최대공약수와 최소공배수라는 문제를 접하게 되었다.

코딩으로는 이걸 어떻게 구하지..?라는 생각이 가장 먼저 들었고 고민해봐도 테케 몇개만 맞고 틀리길래
머릿속이 복잡해져서 솔루션을 여러군데 찾아보고 정리해보고자 한다.

유클리드 호제법

최대공약수를 구할 수 있는 알고리즘으로 유클리드 호제법이라는 것이 있었다.

유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 방법 중 하나로 a > b 일때 a를 b로 나눈 나머지 r에서 b를 r로 나눈 나머지 r1을 구하고 r을 r1로 나눈 나머지를 구하는 것을 반복하면 결국 a와 b의 최대 공약수를 얻을 수 있다는 알고리즘이다.

function solution(n, m) {
    var answer = [];
    
    let a = Math.max(n, m);
    let b = Math.min(n, m);
    
    let c = a * b;
    
    let r;
    
    while(b){
        r = a % b;
        a = b;
        b = r;
    }
    
    c = c / a;
    
    answer.push(a)
    answer.push(c)
    
    return answer;
}

큰 수에서 작은 수를 나눈 나머지를 구해야 하기 때문에 입력받은 두 수 중 큰 수와 작은 수를 알아낼 수 있도록 Math.max, Math.min을 사용하였다.

큰수에서 작은수의 나머지를 구한 값을 r에 담은 후
작은 수에서 r을 나눈 나머지(r1)를 구하고
r에서 r1의 나머지를 구하는 방식을 0이 될 때까지 계속 반복하면 된다.

a와 b를 나눴을 때 나머지가 0이면 b가 최대 공약수가 된다.

최소 공배수

처음 두 수 a, b를 곱한 값에 최대 공약수를 나누면 최소 공배수를 구할 수 있다.

결국은 최대 공약수를 구하는 것이 가장 관건...!

---

처음 봤을 때는 아니 이게 뭐람... 싶었고 지금도 살짝 그런게 남아 있지만 계속 보고 익혀봐야겠다..ㅋㅋ 후ㅜ..ㅠㅠ

---

참고 자료
위키백과 유클리드 호제법