[알고리즘] 최대공약수와 최소공배수

Cottonmycotton·2021년 10월 15일

Algorithm

목록 보기

28/44

문제 설명

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

제한사항

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

입출력 예시

🖊 풀이

이번 문제는 유클리드 호제법을 활용하여 최대공약수, 최소공배수를 모두 구해보았다.

📌 유클리드 호제법이란?

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연> 수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수(또는 정식)
a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 > r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을
r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 > > 최대공약수이다.

최소공배수는 두 수를 곱한 값을 최대공약수로 나누면 된다.

두 수 n과 m의 최솟값과 최대값을 구한다음 변수에 할당해둔다. 대소관계를 정리하기 위함도 있지만 최대공약수를 구할 때 작성될 코드에서 n과 m의 값이 변경되는 이유도 있다.
아래와 같이 배열 [2, 5]로 간단한 예시를 들어보겠다.

📌 최대공약수 구하기

두 수 중 큰수를 작은수로 나누고, 나머지가 0이 될때 까지 값을 나눈다.
- 5 % 2 = 1 -> 나누어 떨어지지 않는다.
- 2 % 1 = 0 -> 나누어 떨어지므로 최대공약수는 1이 된다.

📌 최소공약수 구하기

유클리드 호제법에 따라 위에서 구한 최대공약수를 사용하여 최소공약수를 구해보겠다.
- 2 * 5 / 1 -> 10이 나오므로 2와 5의 최소공배수는 10이 된다.

💡 코드

function solution(n, m) {
  let highNumber = Math.max(n, m);
  let lowNumber = Math.min(n, m);

  let initialization = 0;
  let divisor;
  let multiple;

  while (n !== 0) {
    initialization = m % n;
    m = n;
    n = initialization;
    divisor = m;
  }

  multiple = lowNumber * highNumber / divisor;

  return [divisor, multiple];
}