유클리드 (Euclidean) 알고리즘

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. 참고 자료

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