[JavaScript] 유클리드 호제법 진짜 쉽게 설명해줌 (최대공약수, 최소공배수 구하기, 자바스크립트)

[JavaScript] 유클리드 호제법 진짜 쉽게 설명해줌

유클리드 호제법이란?

• 두 수의 최대공약수를 찾는 “가장 간단하고 효율적인 방법”
• 이제 그냥 최대공약수, 최소공약수 나오면 무조건 이거 쓰세요

---

유클리드 호제법의 사용

두 수 a 와 b 가 있다고 가정해 봅시다. ( a > b ) a를 b로 나눈 나머지를 r이라고 합시다.

이 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 만약 r이 0이 나오는 순간이 있다면, b가 결국 최대공약수가 됩니다.

예시를 들어서 설명해 보겠습니다

48과 36의 최대공약수를 구하려고 합니다 48을 36으로 나눈 나머지는 12입니다

이 때, 48과 36의 최대공약수는 36과 12의 최대공약수와 같습니다

36과 12를 나눈 나머지는 0입니다. 현재 나머지가 0이 나왔으므로, 결국 12는 48과 36의 최대공약수가 됩니다

즉, 계속하여 두 수의 나머지를 구하다 보면, 언젠가는 나머지가 0이 되는 순간이 오는데, 그 때의 ‘나누는 수’ (여기에서는 b) 가 최대공약수가 됩니다

이런 과정을 반복하면서 최대공약수를 찾는 게 유클리드 호제법의 개념입니다

---

유클리드 호제법의 코드 적용 (재귀 적용 안 한 버전)

 

• 최대공약수 구하기

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

• 함수 gcd는 숫자 a와 b의 최대공약수를 구하는 함수입니다
• a와 b를 나눈 나머지를 r에 저장하고, b의 값을 a에, r의 값을 b에 넣어줍니다
• 이 과정을 b가 0이 될 때까지 반복합니다
• b가 0이 되면, a의 값이 최대공약수입니다

 

 

• 최소공배수 구하기

function lcm(a, b) {
    return a * b / gcd(a, b);
}

• 최소공배수를 구하는 공식은 두 수의 곱 / 최대공약수 입니다

---

유클리드 호제법의 코드 적용 (삼항연산자, 재귀 활용)

 

• 최대공약수 구하기

const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));

• a와 b의 나머지가 0이라면, 그 때의 b를 반환합니다
• 이러한 조건을 만족하지 못한다면, gcd 함수를 재귀적으로 실행합니다
  • 이 때의 a는 이전의 b가 되며, b는 이전의 r이 됩니다

 

•  최소공배수 구하기

const lcm = (a, b) => (a * b) / gcd(a, b);

• 아까와 똑같은 로직입니다

---

문제에 활용하기

최대공약수, 최소공배수 문제가 있으니 문제를 풀면서 적용시켜 보세요

[Algorithm] 최대공약수와 최소공배수 (유클리드 호제법 사용) - 프로그래머스