[ Lv. 1 ] 최대공약수와 최소공배수 - JavaScript

문제 설명

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

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

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

입출력 예 설명

• 입출력 예 #1
  위의 설명과 같습니다.
• 입출력 예 #2
  자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

내풀이

function solution(n, m) {
    let gcd = 1;
    for(let i = 2; i <= Math.min(n, m); i++){
        if(n % i === 0 && m % i === 0){
            gcd = i;
        }
    }
    const lcm = n * m / gcd;
    return [gcd, lcm];
    
}

 

문제 해결 과정

최대공약수와 최소공배수에 대한 정의를 하고, n과 m의 값을 받을 때 gcd를 구하는 함수와 lcm을 구하는 함수를 각 반환 되는 값으로 전달하는 방식으로 접근하기로 했다. 두 기능의 역할이 다르기 때문에 이를 함수로 분리해주는 것이 좋지 않을까 하는 생각에서 이렇게 접근했다.

최대공약수(GCD, Greatest Common Divisor) : 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. 예를들어 72와 30의 최대 공약수는 6이 된다.

최소공배수(LCM, Least Common Multiple) : 두 자연수의 공통된 배수 중 가장 작은 수를 의미하며, 최소공배수는 두 인수의 곱을 한 후 그 값을 최대공약수로 나누면 구할 수 있다. 위의 예시를 가져와 이용한다면 72와 30의 곱은 2160이고 최소 공약수는 6이므로 이를 나누면, 최소공배수는 360이 된다.

2개의 자연수를 받아서 최대공약수가 될 때 까지 2부터 두 자연수 중 작은 자연수까지 모두 나누면 최대 공약수를 구할 수 있다. 위 같은 방법으로 문제를 풀면 시간 복잡도는 O(n)가 되며, 이 문제 해결 방법보다 효율성이 더 좋은 알고리즘이 있으므로 이에 대해 알아보도록 하자.

---

다른 방법 ( 유클리드 호제법을 이용한 방법 )

유클리드 호제법 : 두 수의 최대 공약수를 구하는 알고리즘으로 보통 최대 공약수를 구하기 위해서는 소인수분해를 해서 공통된 소수를 찾는 작업을 수행해야하는데, 수가 커질수록 이 과정이 효율적이지 못해서 보다 나은 방법으로 구할 수 있도록 해준다. 이 방식을 적용했을때의 시간 복잡도는 O(log n)이다.

두 값을 나눈 나머지를 구하는 연산을 반복하는 과정으로 단계는 다음과 같다. 

1. 큰 수를 작은 수로 나눈 나머지를 구한다. (72 % 30)

2. 나누었던 수(B)와 그 나머지(A % B의 결과인 12)로 다시 나머지 연산을 한다.

3. 이 과정을 나머지(A % B)가 0이 될 때까지 반복하며, 0이 된 시점에서의 첫 피연산자(B = 6)가 최대 공약수가 된다.

예시 : 72와 30의 최대공약수를 유클리드 호제법을 이용해서 구하는 방법을 테이블로 표현하면 아래와 같다.

GCD(A, B)	A	B	A % B
GCD(72, 30)	72	30	12
GCD(30, 12)	30	12	6
GCD(12, 6)	12	6	0

A % B가 0이 되는 순간 B의 값이 최대 공약수가 된다.

위 테이블로 봤을 때는 A % B가 0이 되는 시점의 B가 6이 되므로 최대 공약수가 6임을 확인할 수 있다.

function solution(n, m) {
    return [gcd(n, m), lcm(n, m)];
}
const gcd = (a, b) => b ? gcd(b, a % b) : a;
const lcm = (a, b) => a * b / gcd(a, b);

따라서, a > b라고 할 때 b가 0이 될 때까지 나머지 연산을 수행하도록 하면 되는데 이는 반복문을 이용하거나 재귀함수를 이용하는 방법이 있다. 내가 구한 방식은 재귀함수를 이용해서 gcd와 lcm 함수로 분리하고, 반환 값에서 인자를 받아서 구할 수 있도록 했다. 

b가 0이 아니라면, 나머지 연산을 재귀적으로 수행하고(이때, 첫 번째 인자가 B가 되고, 두 번째 인자가 그 루프 시점의 a  % b 결과 값이 된다.), 0이라면 a(이전 루프의 a % b 결과 값)를 반환한다.  

lcm은 두 인자를 곱하고 최대공약수로 나누면 되기 때문에, lcm 함수 안에 gcd 함수를 호출해서 최소공배수를 구할 수 있도록 했다.

이외에도 반복문으로도 유클리드 호제법 알고리즘이 적용된 gcd 구하는 방법으로는 아래와 같이 구현할 수도 있다.

function gcd(a, b) {
    let temp;
    while(b) {
    	temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

마찬가지로 b가 0이 되는 조건으로, b가 0이 아니라면 while문으로 루프를 진행하면서 temp 안에는 a % b의 값을 할당하고, a에는 b의 값을, b에는 temp(a % b)의 값으로 저장한다. 그리고 만약 b가 0이 되면, 그때 a(이전 루프의 a % b 결과 값)를 반환한다.

---

참조

[ Wikipedia - 유클리드 호제법 ] 
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

[ Velog - 유클리드 호제법 ]
https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법(Euclidean-algorithm)