유클리드 호제법

• 백준의 정수론 문제를 살펴보다, 유클리드 호제법에 대해 알게 되었다.
• 어떤 것인지 간단하게 파악하고, 이를 이용해 문제를 푼 것에 대해 짤막히 기록한다.

---

유클리드 호제법

• 자연수 혹은 정수 사이의 최대공약수(Greatest Common Denominator: GCD)를 구하기 위한 알고리즘.
• a와 b의 최대공약수는, a / b의 나머지 r과 b의 최대공약수와 같다.

  이를 실제 함수로 구현하면 재귀 혹은 반복을 통해 구현할 수 있다. 나는 아래와 같은 코드를 작성해 문제풀이에 활용하였다.

 

const getGCD = (a, b) => {
  if (a === b) return a;
  if (a === 1 || b === 1) return 1;

  if (b === 0) return a;

  return getGCD(b, a % b);
};

 

문제 풀이

  개념을 간단하게 파악하고 간단한 문제 풀이를 해보았다.

 

백준 1934번

  말그대로 최소공배수를 구하는 문제. 위에서 공부한 유클리드 호제법은 두 수 사이의 최대공약수를 구하는 알고리즘이지만, a와 b사이의 최소공배수는 두 수를 곱한 것을 최대공약수로 나누면 도출*되므로 이에 활용할 수 있다.

 

* 참고

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

최소공배수 - 위키백과, 우리 모두의 백과사전

 

   따라서 유클리드 호제법을 사용하여 최대공약수를 구하고, 위에서 언급한대로 최소공배수를 계산하면 된다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

let answer = "";

const getGCD = (a, b) => {
  if (a === b) return a;
  if (a === 1 || b === 1) return 1;

  if (b === 0) return a;

  return getGCD(b, a % b);
};

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  for (let i = 1; i < input.length; i++) {
    let a = input[i][0];
    let b = input[i][1];
    if (a === 1 || b === 1) {
      answer += `${a === 1 ? b : a}\n`;
    } else {
      const gcd = getGCD(a, b);

      if (gcd === 1) answer += `${a * b}\n`;
      else {
        const leastMultiple = (a * b) / gcd;
        answer += `${leastMultiple}\n`;
      }
    }
  }

  console.log(answer.trim());

  process.exit();
});

 

백준 1735번

  두 분수를 더하고, 그 결과를 기약분수로 나타내는 문제. 입력받은 두 분수를 더한 다음, 분자와 분모의 최대공약수를 구해 분모/분자를 나누면 기약분수를 쉽게 구할 수 있다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const getGCD = (a, b) => {
  if (a === b) return a;
  if (a === 1 || b === 1) return 1;

  if (b === 0) return a;

  return getGCD(b, a % b);
};

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  let denominator = input[0][1] * input[1][1];
  let numerator = input[0][0] * input[1][1] + input[1][0] * input[0][1];

  const gcd = getGCD(denominator, numerator);

  console.log(numerator / gcd, denominator / gcd);

  process.exit();
});

 

백준 2485번

  임의의 간격으로 심어진 가로수 사이 최소한의 나무만을 심어 나무 사이 간격이 똑같아지도록 만드는 문제. 나무 사이의 간격을 구하고, 간격들 간의 최대공약수를 구하면 된다는 것을 파악했으나 두 개 이상의 수에 대해 최대공약수를 어떻게 구하면 될지 몰라 망설이던 중, N개의 수에 대해 최대공약수를 구하는 방법에 대해 알게 되었다. 첫 두 수의 최대공약수를 구한 후, 그 최대공약수와 다음 수의 최대공약수를 구하는 것을 반복하면 N개의 수의 최대공약수를 구할 수 있다고.

 

  이를 유클리드 호제법을 사용해 구현하여 문제를 푼 코드가 아래와 같다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const getGCD = (a, b) => {
  if (a === b) return a;
  if (a === 1 || b === 1) return 1;

  if (b === 0) return a;

  return getGCD(b, a % b);
};

rl.on("line", (line) => {
  input.push(parseInt(line));
}).on("close", function () {
  const distance = [];

  // 나무 사이의 간격을 구함
  for (let i = 1; i < input.length - 1; i++) {
    distance.push(input[i + 1] - input[i]);
  }

  let gcd = distance[0];

  // 간격들의 최대공약수를 구함
  for (let j = 1; j < distance.length; j++) {
    gcd = getGCD(gcd, distance[j]);
  }

  console.log((input[input.length - 1] - input[1]) / gcd + 1 - input[0]);
  process.exit();
});

---

• 평소 백준의 단계별로 풀어보기를 애용하는 편인데, 다양한 유형의 문제를 접하고 모르던 개념을 알 수 있어 무척 유용한 것 같다.