[코딩테스트] 최대공약수와 최소공배수

저번에도 똑같은 게시물을 쓴것 같은데 그때는 솔직히 대충 보고 넘어갔던거라, 

이번에 제대로 이해하고 정리해두려고 글을 남긴다. 

사실 제일 간단한 방법은 최대공약수를 구하려면 그냥 1부터 주어진 수 중 작은 수까지 있는 애들을 싹 다 나눠보고 나머지가 0인 애들 추린 다음에 그중 제일 큰거 꺼내면 된다.

근데 이렇게 하면 코드도 길어지고, 오류가 꽤 생긴다. 1은 무조건 나눠떨어지니 1이 계속 추가 된다던가 하는 문제가 생기는데, 그거 극복하려면 유클리드 호제법이라고 불리는걸로 계산 하는게 속편하다.

 

유클리드 호제법
작은 수를 큰 수로 나눠서 나머지가 0이 아니면 그 나머지로 큰 수를 나눈다. 이 과정을 반복하다가 나머지가 0이 되었을 때 큰 수가 최대공약수다.

 

말로 써두니까 상당히 복잡한 느낌이 드는데 코드로 보면 확 잘 보일 것 같다. 

 

function gcd (min,max) { // 최대공약수를 구하는 함수
    return min % max === 0 ? max : gcd(max , min % max) // 여기가 내가 말한 원리
}

function solution(n, m) {
    var answer = [];
    const max = Math.max(n,m); // 주어진 수 중 큰 수 찾기
    const min = Math.min(n,m); // 주어진 수 중 작은 수 찾기
    const gcdValue = gcd(min, max);
    const lcmValue = (n * m)/gcdValue; // 최소공배수는 주어진 수 두개를 곱하고 최대공약수로 나누면 된다.
    answer[0]=gcdValue;
    answer[1]=lcmValue;
    return answer;
}

 

저 유클리드 호제법 걍 외우는게 나을 것 같다. 최대공약수, 최소공배수 개념은 어딜 가든 필요할 것 같고..

결국 코드를 쓰는 것도 수학에 기반하는게 많기 때문에, 수학적인 개념 조금씩 다시 떠올려야겠다. 

고등학생때로 돌아온 것 같네 에휴..