[FE - ConnecTo] DAY41 TIL👩🏻‍💻

22.09.06 스스로 공부한 내용들을 정리하였습니다 😊
피드백은 언제나 환영입니다! 🍊

오늘 아침에 최소공배수, 최대공약수 문제를 푸려고 들어갔다가, 무언가 어떠한 알고리즘이 존재할 것 같아서 검색해 본 결과, 이 둘을 구하기 위해서 유클리드 호제법이라는 알고리즘이 존재한다는 것을 알게 되었습니다.

그래서 이를 공부해보았습니다.

유클리드 호제법이란?

유클리드 호제법은 어떤 두 자연수의 최대공약수를 구하는 알고리즘의 하나로, 최대공약수를 구하는 알고리즘 중 가장 대표적인 알고리즘입니다.

여기서 호제법이란 무엇일까요?

호제법이란, 주어진 두 수로 서로 다른 수를 나누어 원하는 결과를 얻는 방법을 의미합니다.

그래서 유클리드 호제법은

어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다

는 성질을 이용한 알고리즘입니다.

이 원리에 따라, a를 b로 나눈 나머지를 다시 a로 사용하고, b로 나누기를 반복하다, 나누어 떨어질 때 나눈 수가 바로 두 수의 최대 공약수가 되는 것입니다.

코드를 살펴볼까요?

let N = 24, M = 18;

function gcd(a, b) {
  while (b !== 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}

let gcd = gcd(N, M);
let lcm = (N * M) / gcd;

여기서 gcd가 최대공약수이고, lcm은 최소공배수입니다.

최소공배수의 경우, 최대공약수를 구할 수 있다면, 비교적 쉽게 접근이 가능합니다.

그 이유는, 최소공배수는 주어진 두 수를 곱한 후, 최대공약수로 나누어주면 되기 때문입니다.