[Programmers #12940] - 최대공약수와 최소공배수]

(Lv. 1) 최대공약수와 최소공배수 (문제 링크)

문제 설명

두 개의 정수 n과 m이 주어졌을 때, 두 수의 최대공약수와 최소공배수를 배열 형태로 return하는 solution 함수를 완성하라.

배열의 앞에는 최대공약수를, 뒤에는 최소공배수를 넣어 반환한다.

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

제한 조건

1. 두 수는 1 이상, 1,000,000 이하인 자연수다.

입출력 예시

---

접근 방식

1. 입력값 : 자연수 2개 / 출력값 : 두 수의 [최대공약수, 최소공배수] 배열
2. 최대공약수(GCD: Greatest Common Divisor) : 공약수 중 가장 큰 수
   2-1. 주어진 자연수들을 공약수로 나눴을 때 모두 나누어 떨어진다.
   2-2. 공약수는 입력값으로 주어진 값 중 최소값보다 클 수 없다.
   2-3. 따라서, 입력값들 중 작은 수를 구한 뒤, 1부터 해당 수까지 반복문을 수행하여 나눠지는 가장 큰 수를 반환한다.
3. 최소공배수(LCM: Least Common Multiple) : 공배수 중 가장 작은 수
   3-1. 최소공배수의 법칙
   : 2개의 자연수 a, b에 대하여, a와 b의 최소공배수는 a * b를 최대공약수로 나눈 값과 같다.

코드

function solution(n, m) {
  let answer = [];
  let gcd = 0;
  let lcm = 0;

  for (let i = 1; i <= Math.min(n, m); i++) {
    if (n % i === 0 && m % i === 0) {
      gcd = i;
    }
  }

  lcm = (m * n) / gcd;

  answer = [gcd, lcm];

  return answer;
}

---

시행착오

최소공배수를 구하는 방법

초기 접근 방식

1. 공배수를 주어진 자연수들로 나눴을 때 모두 나누어 떨어진다.
2. 공배수는 입력값으로 주어진 값 중 최대값보다 작을 수 없다.
3. 따라서, 입력값들 중 큰 수를 구한 뒤 주어진 입력값들로 나눠지는 가장 작은 수를 반환한다.

• 문제점
  : 3번 과정을 어떻게 수행해야 할지 감이 잡히지 않았다.

• 해결 방법
  : 해결한 사람들의 코드를 참고하여 최소공배수의 법칙이 존재한다는 사실을 깨달았다.

  최소공배수의 법칙
  : 2개의 자연수 a, b에 대하여, a와 b의 최소공배수는 a * b를 최대공약수로 나눈 값과 같다.

---

개선할 수 있는 부분

최대공약수를 구하는 방법

유클리드 호제법(Euclidean Algorithm)
: 2개의 자연수 a, b에 대하여, a % b === r 이면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

사용 방법

// 1. 재귀함수 ver.
function gcd(a, b) {
  if (Math.min(a, b) === 0) return Math.max(a, b);
  else return gcd(Math.min(a, b), Math.max(a, b) % Math.min(a, b));
}

// 2. 반복문 ver.
function gcd(a, b) {
  let max = Math.max(a, b);
  let min = Math.min(a, b);
  while (max % min !== 0) {
    let r = max % min;
    max = min;
    min = r;
  }
  return min;
}

---

주요 개념

• 최소공배수의 법칙
• 최대공약수의 법칙(유클리드 호제법)