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

James An·2022년 8월 31일

Algorithm

목록 보기

1/1

유클리드 호제법이란?

유클리드 호제법은 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.라는 성질을 활용하여 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 방법이다.

호제법이란 두 수가 서로를 나누어서 원하는 수를 얻는 알고리즘이다.

최대 공약수 구하기

a와 b를 나눈 나머지를 r이라고 하자. (a >= b, 0 <= r < b)
이 때 a와 b의 최대 공약수를 (a, b)라고 한다면 다음이 성립한다.
(a, b) = (b, r)
이후 나머지가 0이 될 때까지 위 방법을 반복하면 최대 공약수를 구할 수 있다.

//  JavaScript
//  유클리드 호제법
function findGcd(a, b) {
	const remainder = a % b
    if (remainder === 0)
        return b
    return findGcd(b, remainder);
}

// 일반적인 방법
function findGcd(a, b) {
    let gcd = 1;
    for (let i = 2; i <= Math.min(a, b); i++)
    {
        if (a % i === 0 && b % i === 0)
            gcd = i;
    }
    return (gcd);
}

유클리드 호제법의 경우 나머지(remainder)가 0이 될때까지 재귀로 동작한다.
일반적인 방법은 2부터 시작하여 min(a, b)까지 모든 정수로 두 수를 나누는 방법이 있다. 하지만 모든 정수를 나눠야하기때문에 시간 복잡도는 0(N)이 된다. 반면에 유클리드 호제법의 경우 O(logN)의 시간 복잡도를 가진다.

최소 공배수 구하기

// JavaScript
// 유클리드 호제법
let lcm = (a * b) / findGcd(a, b);

// 일반적인 방법
function findLcm(a, b) {
    let lcm = 1
    while (42)
    {
        if (lcm % a === 0 && lcm % b === 0)
            break ;
        lcm++;
    }
    return lcm;
}

LCM을 구하는 일반적인 방법은 두 수로 나눠지는 수를 찾을 때까지 모든 정수에 대해 나눠보는 방법이 있다.
a, b에 대해서 최소 공배수와 최대 공약수는 a * b === GCD * LCM 관계가 성립한다.
따라서, 최소 공배수는 a * b / GCD를 사용해 구할 수 있다.

예시 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12940
두 수를 입력받아 두 수의 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM)를 담은 배열을 반환하는 함수를 만드는 문제를 통해 유클리드 호제법을 직접 실습해볼 수 있다.

Solve

  function findGcd(a, b) {
      const remainder = a % b
      if (remainder === 0)
          return b
      return findGcd(b, remainder);
  }

  function solution(a, b) {
      let answer = [];
      let gcd = findGcd(a, b);
      let lcm = (a * b) / gcd;
      answer.push(gcd);
      answer.push(lcm);
      return answer;
  }

출처

James An

born 2 code :)