유클리드 호제법 - 최대공약수, 최소공배수

여러분은 최대공약수, 최소공배수를 어떻게 구하고 계신가요?
for문 돌려서 알아내도 되지만 효율성이 떨어진다는 문제가 있죠 ㅠㅠ
이러한 문제를 해결할 수 있는 알고리즘이 존재합니다👏🏻

최대공약수, 최소공배수를 효율적으로 구할 수 있는 유클리드 호제법에 대해 공부했습니다😊

---

(일반적인) 최대공약수 구하기

• 최대공약수(Greatest Common Divisor, GCD): 두 정수의 공약수 중 가장 큰 것
  ex) 8, 12의 공약수는 1, 2, 4이다. 이때 최대공약수는 4이다.

➡️ 몫을 1부터 두 수 중 작은 수까지 증가시켜가며 두 수의 나머지가 모두 0이 되는 값을 찾기(공약수).
이때 공약수 중 가장 큰 값이 최대공약수가 된다.

const a = 8;
const b = 12;
const 공약수 = [];

for (let i = 1; i < a; i++) { // i의 최대값은 a, b 중 작은 값보다 클 수 없음
  if (a % i === 0 && b % i === 0) {
    공약수.push(i);
  }
}

const 최대공약수 = 공약수[공약수.length - 1]; // 공약수의 가장 큰 값 = 최대공약수

(일반적인) 최소공배수 구하기

• 최소공배수(Least Common Multiple, LCM): 두 정수의 양의 공배수 중 가장 작은 것
  ex) 8, 12의 공배수는 24, 48, 72, 96, 120, ... 이다. 이때 최소공배수는 24이다.

➡️ 나눌 값을 둘 중 더 큰값부터 시작하여 증가시켜가며 두 수로 나눈다. 이때 처음으로 둘 다 나머지가 0이 나온 값이 최소공배수가 된다.

const a = 8;
const b = 12;
const 공배수 = [];

while (공배수.length < 3) { // 공배수는 무한으로 나오기 때문에 제약 건 것
  for (let i = b; ; i++) { // i의 시작값은 a, b 둘 중 더 큰 값 이하로 내려갈 수 없음, i의 최대값은 정할 필요 없음
    if (i % a === 0 && i % b === 0) {
      공배수.push(i);
    }
  }
}

const 최소공배수 = 공배수[0]; // 공배수의 가장 작은 값 = 최소공배수

유클리드 호제법을 이용한 최대공약수

• 유클리드 호제법(Euclidean algorithm): 두 정수의 최대공약수를 구하는 알고리즘

➡️ 두 수 중 큰 수를 작은 수로 나눈다. 이때 나머지(L)가 0이면 더 작은 수가 최대공약수가 된다. (a % b = L, L !=0)
나머지(L)가 0이 아니면, 두 수 중 작은 수를 나머지(L)로 나눈다. 이때 나머지(M)가 0이면 나머지(L)가 최대공약수가 된다. (b % L = M, M !=0)
나머지(M)도 0이 아니면, 나머지(L)을 나머지(M)으로 나눈다. (L % M = N)
이 과정을 반복하며 나머지가 0이 나올 때까지 찾는다. 이때 최대공약수는 나누어지는 수가 된다.

let a = 8;
let b = 12;
let 나머지 = 12 % 8;

while (나머지 != 0) {
  a = b;
  b = 나머지;
  나머지 = a % b;
}

const 최대공약수 = b;

유클리드 호제법을 이용한 최소공배수

유클리드 호제법을 이용해 최대공약수를 구한 다음, 이 값을 이용해 최소공배수를 구할 수 있다.
=> 여러 수의 최소공배수도 구할 수 있다. 2개씩 짝지어 최소공배수를 구해가다보면 최종 2개만 남을 것이고, 그때 최종 최소공배수를 구하면 된다.

➡️ 두 수를 곱한 후, 곱한 값을 최대공약수로 나눈다. 그 값이 최소공배수가 된다.

let a = 8;
let b = 12;
const axb = a * b;
let 나머지 = 12 % 8;

while (나머지 != 0) {
  a = b;
  b = 나머지;
  나머지 = a % b;
}

const 최대공약수 = b;
const 최소공배수 = axb / 최대공약수;

응용 문제: 백준 1735번

백준 1735번 바로가기

//통과 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [num1, num2] = fs.readFileSync(filePath).toString().trim().split("\n");
let [a1, b1] = num1.split(" ");
let [a2, b2] = num2.split(" ");

let finalA = 0;
let finalB = 0;

if (b1 == b2) {
  finalA = +a1 + +a2;
  finalB = +b1;
} else {
  finalB = +b1 * +b2;
  let newA1 = +a1 * +b2;
  let newA2 = +a2 * +b1;
  finalA = newA1 + newA2;
}

let bigNum = Math.max(finalA, finalB);
let smallNum = Math.min(finalA, finalB);
let remain = bigNum % smallNum;

while (remain != 0) {
  bigNum = smallNum;
  smallNum = remain;
  remain = bigNum % smallNum;
}

let gcd = smallNum;

if (gcd == 1) return console.log(finalA + " " + finalB);

finalA = finalA / gcd;
finalB = finalB / gcd;
console.log(finalA + " " + finalB);