최대 공약수, 최소 공배수, 유클리드 알고리즘

출처: https://ljtaek2.tistory.com/144

[level1] - 최대공약수와 최소공배수(유클리드 호제법)

문제 설명 :

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

 

입출력 예 :

n	m	return
3	12	[3, 12]
2	5	[1, 10]

접근 방법 :

이 문제를 풀기 전에 먼저 최대공약수와 최소공배수를 알아야 한다.

최대공약수란?

두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

예를 들어, 5와 10의 약수는 각각

ex) 5는 1, 5

ex) 10은 1, 2, 5, 10

즉, 약수 중 공통인 수 가운데 가장 최대인 수는 5이므로 최대 공약수는 5라 할 수 있다. 

 

최소공배수란?

예를 들어 또 5와 10이 있고, 각각의 배수는

ex) 5는 5, 10, 15, 20, 25...

ex) 10은 10, 20, 30, 40, 50...

즉, 공통인 배수들 중에 가장 최소인 수는 10이므로 최소 공배수는 10이라 할 수 있다.

 필자는 우선 최대공약수를 구하기 위해 유클리드 호제법을 활용해서 구해 볼 것이다.

유클리드 호제법이란?

두 수가 서로 상대방 수를 나눠서 결국 원하는 수를 얻는 알고리즘을 말하며, 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.

즉, 두 수 A와 B가 있으면 서로의 수를 나누어가기를 반복하며 나머지가 0이 되었을 때의 나누는 수가 A와 B의 최대공약수이다.

예를 들어, 2개의 자연수 58과 18가 있다. (단, a > b)

No.	GCD(A, B)	A	B	A%B
1	GCD(58,18)	58	18	4
2	GCD(18,4)	18	4	2
3	GCD(4,2)	4	2	0

해당 순서대로 두 수를 계속 나누고 나머지가 0이 되는 순간 B의 수가 최대공약수가 된다.

즉 최대공약수 구하는 방식을 코드로 나타내면, 밑에 처럼 나머지가 0이 될 때까지 재귀 함수를 이용한 로직이 나온다.

function solution(n, m) {
    const GCD = getGCD(Math.max(n, m),Math.min(n,m));
    return GCD;
}
const getGCD = (n, m) => {
    return m === 0 ? n : getGCD(m, n % m);
}

 

그다음 최소공배수를 구하는 것은 어렵지 않다.

최소공배수(LMC) = 두 수의 곱한 값 / 최대공약수(GCD)

두 수를 곱한 값과, 두 수의 최대공약수를 나누면 최소공배수가 나온다.

최대공약수와 최소공배수를 구했기 때문에, 이제 배열에 순서대로 push()해서 순서대로 추가하고 반환하면 된다.

이를 통해 최종적으로 다음과 같은 로직을 짜보았다.

 

내가 짠 코드 :

function solution(n, m) {
    let ansewer = [];
    const GCD = getGCD(Math.max(n, m),Math.min(n,m));
    ansewer.push(GCD);
    const LCM = getLCM(n * m ,GCD);
    ansewer.push(LCM);
    return ansewer;
}
const getGCD = (n, m) => {
    return m === 0 ? n : getGCD(m, n % m);
}

const getLCM = (a, b) => {
    return a / b;
}