[프로그래머스 | JS] lv.1 최대공약수와 최소공배수

최대 공약수(Greatest Common Divisor) & 최소 공배수(Largest Common Multiple)

 

최대 공약수(GCD)

• 정수인 두 수의 공약수 중 가장 큰 수 
• 즉, 두 수를 동시에 나눌 수 있는 수 중에 가장 큰 수
• Math.min(a,b)를 활용해 둘 중에 작은 수의 범위를 넘어가지 않게하여 불필요한 연산 제거

최소 공배수(LCM)

• 정수인 두 수의 공배수 중 가장 작은 수 
• 즉, 두 수를 곱한 값을 최대 공약수로 나눈 수 (a * b / a와b의 최대 공약수)
• 두 수의 최대 공약수만 알아도 최소 공배수를 구할 수 있다.

최적화 하는 알고리즘: 유클리드 호제법

{관련 내용 정리 요망}

 

내 풀이

{
  function solution(n, m) {
    let gcd = 1;
    let lcm;

    //i = 2, 최대 공약수는 1보다 큰 자연수 중 가장 작은 값이기 때문
    // n, m의 최대공약수는 n과 m중 작은 값보다 큰 수가 될 수 없기 때문에 Math.min() 활용
    for (let i = 2; i <= Math.min(n, m); i++) {
      if (n % i === 0 && m % i === 0) gcd = i;
    }
    lcm = (n * m) / gcd;

    return [gcd, lcm];
  }
}

 

위의 코드는 매개변수로 주어진 두 수의 크기가 커지면 성능 문제를 일으킬 수 있다. 

유클리드 알고리즘을 적용한 코드 예시

function solution(n, m) {
    let a = Math.max(n, m);
    let b = Math.min(n, m);
    let r = a % b;

    // while문에서 유클리드 알고리즘을 반복적으로 수행하여 최대 공약수 찾기
    // b = 최대공약수 저장
    while (r > 0) {
      a = b;
      b = r;
      r = a % b;
    }
    const gcd = b;
    const lcm = (n * m) / gcd;
    return [gcd, lcm];
  }

유클리드 알고리즘 코드 설명

1. a와 b중 큰 값을 a에 저장하고 작은 값을 b에 저장한다.
2. a를 b로 나눈 나머지를 구한다.
3. 나머지가 0이면 b가 `최대공약수(GCD)`가 된다.
4. 나머지가 0이 아니면 b를 a로, 나머지를 b로 대체하고 2번으로 돌아간다. 

 최소공배수 = 두 수의 곱 / 최대공약수