유클리드 (Euclidean) 알고리즘

유클리드 (Euclidean) 알고리즘에 대해 정리한 페이지입니다.

Posted Mar 4, 2024

By HyunJinNo

Tags

Algorithm

1. 개요

유클리드(Euclidean) 알고리즘에 대해 정리한 페이지입니다.

2. 유클리드 (Euclidean) 알고리즘

2.1. 개념

유클리드(Euclidean) 알고리즘은 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는데 사용되는 알고리즘입니다. 유클리드 알고리즘은 두 자연수 a, b(a > b)에 대해 a와 b의 최대공약수는 b와 a % b의 최대공약수과 같다는 점을 이용합니다. 즉, GCD(a, b)= GCD(b, a % b)라는 식이 성립하며, 나머지 b가 0이 될 때까지 반복하여 최대공약수를 구하게 됩니다.

2.2. 구현

2.2.1. 최대공약수 (Greatest Commmon Divisor, GCD)

1int gcd(int a, int b) {
2    if (b == 0) {
3        return a;
4    } else {
5        return gcd(b, a % b);
6    }
7}

1fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

1/**
2 * @param {number} a
3 * @param {number} b
4 */
5const gcd = (a, b) => {
6  if (b === 0) {
7    return a;
8  } else {
9    return gcd(b, a % b);
10  }
11};
12
13const a = 21;
14const b = 15;
15
16console.log(gcd(Math.max(a, b), Math.min(a, b))); // 3

2.2.2. 최소공배수 (Least Common Multiple, LCM)

1/**
2 * @param {number} a
3 * @param {number} b
4 */
5const gcd = (a, b) => {
6  if (b === 0) {
7    return a;
8  } else {
9    return gcd(b, a % b);
10  }
11};
12
13const a = 21;
14const b = 15;
15
16const lcm = (a * b) / gcd(Math.max(a, b), Math.min(a, b));
17console.log(lcm); // 105

3. Example

• 9613번: GCD 합

  javascript

  1const path =
  2  process.platform === "linux" ? "/dev/stdin" : "./algorithm/input.txt";
  3const input = require("fs").readFileSync(path).toString().split("\n");
  4const t = Number(input[0]); // 테스트 케이스의 수, 1 <= t <= 100
  5
  6/**
  7 * @param {number} a
  8 * @param {number} b
  9 */
  10const gcd = (a, b) => {
  11  if (b === 0) {
  12    return a;
  13  } else {
  14    return gcd(b, a % b);
  15  }
  16};
  17
  18for (let i = 1; i <= t; i++) {
  19  const temp = input[i].split(" ").map(Number);
  20  const [n, arr] = [temp[0], temp.slice(1)];
  21  let result = 0;
  22
  23  for (let j = 0; j < n; j++) {
  24    for (let k = j + 1; k < n; k++) {
  25      result += gcd(arr[j], arr[k]);
  26    }
  27  }
  28
  29  console.log(result);
  30}

4. 참고 자료

• 유클리드 호제법 - 나무위키