[Algorithm 028] JS - 최대공약수와 최소공배수 (Level 01)

문제 출처 : 프로그래머스 prorammers  - 평균 구하기 (링크)

 

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한사항

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

 

---

 

일단 초등수학교육을 까마득히 잊고 지내서,

최대공약수와 최소공배수가 뭔지 기억이 안납니다...🥲

공약수가..뭐? 서로소??

 

 

이렇게 정리하니 한결 보기편해졌다.

 

최대공약수 : 두 수를 완벽히 나누어 떨어지게 (나머지가 0이게)할 수 있는 제일 큰 수

36 / 12 = 3
24 / 12 = 2

최소 공배수

 

 

A.  내가 푼 답

function solution(n, m) {
  var answer = [];
  let greatestCommoFactor = 0;
  let leastCommoMultiple = 0;

  if (n % m === 0 || m % n === 0) {
    greatestCommoFactor = Math.min(n, m);
    leastCommoMultiple = Math.max(n, m);
  } else {
    for (let i = 1; i < Math.max(n, m); i++) {
      if (n % i === 0 && m % i === 0) {
        greatestCommoFactor = i;
      }
    }

    leastCommoMultiple = (n * m) / greatestCommoFactor;
  }

  answer.push(greatestCommoFactor, leastCommoMultiple);
  return answer;
}

 

 

1. 두 가지 조건 걸어주기

조건 1)

// 예
n=12, m=3

위의 예와 같이 주어진 두 수가 서로에 의해 완전히 나누어질 경우,

• 둘 중 작은 수가 '최대공약수'
• 둘 중 큰 수가 '최소공배수'

 

 

조건 2)

// 예
n=36, m=24

조건 1을 만족하지 않을 경우

 

최대공약수 구하기

• 최대공약수는 두 수 모두를 나누어 떨어지게 할 수 있는 최대의 수이다.
  즉, 어떤 수 i로 나눌 때
  36 % i == 0, 24 % i == 0 을 만족해야한다.
• for문과 &&연산자를 사용해서, 조건을 만족하는 수 중 제일 큰 숫자를 '최대공약수'로 지정

최소공배수 구하기

• 최대 공약수 12는 구해 졌고,
  여기서 최소 공배수를 구하려면 아래와 같이 3, 2 또는 이 두 수를 곱한 6이라는 수가 필요하다.

• 가만 보면 3, 2 라는 이 두 수도 결국 주어진 수 n, m을 최대공약수로 나눈 것이다.

36 / 12 = 3
24 / 12 = 4 

// greatestCommoFactor = 12

leastCommoMultiple = a * b

a = n / greatestCommoFactor;
b = m / greatestCommoFactor;

하지만 우리는 a, b를 곱한 값이 필요한 것이므로, 값을 따로 구할 필요 없이 한 번에 구할 수 있다.

 leastCommoMultiple = (n * m) / greatestCommoFactor;

 

 

 

B. 다른 사람의 풀이

function greatestCommonDivisor(a, b) {return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);}
function leastCommonMultipleOfTwo(a, b) {return (a * b) / greatestCommonDivisor(a, b);}
function gcdlcm(a, b) {
    return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)];
}

 

최대공약수를 구하는 알고리즘으로 유클리드호제법 이라는 것이 있다고 한다. (참고 velog @YeYelog)

 

유클리드 호제법 : 두 수의 최대공약수를 구하는 알고리즘 
호제법 : 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘
MOD연산 : 두 값을 나눈 나머지를 구하는 연산

 

유클리드 호제법

1. 큰 수를 작은 수로 나눔

 

    36 % 24 == 12

 

2. 나눴던 수를 나머지로 나눔

    24 % 12 == 0

 

3. 반복

4. 나머지가 0이 됐을 때, 나누는 수로 사용된 12가 36과 24의 최대공약수가 됨

 

 

새로 알게된 것들

• for 문을 사용하지 않고, 삼항연산자에 조건을 걸어 재귀함수를 사용하는 스킬...😨
• Math.abs() : 주어진 숫자의 절대 값을 반환

Math.abs(12)   // 12
Math.abs(0)    // 0
Math.abs(-12)  // 12