Search
Duplicate
🐬

유클리드 호제법으로 최대 공약수(GCD) 최소 공배수(LCM) 구하기

간단소개
팔만코딩경 컨트리뷰터 (Library DB (속성)에 관계됨)에 관계됨
ContributorNotionAccount
주제 / 분류
Algorithm
Javascript
태그
Scrap
8 more properties

유클리드 호제법이란?

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

최대 공약수 구하기

ab를 나눈 나머지를 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); }
JavaScript
유클리드 호제법의 경우 나머지(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; }
JavaScript
LCM을 구하는 일반적인 방법은 두 수로 나눠지는 수를 찾을 때까지 모든 정수에 대해 나눠보는 방법이 있다.
a, b에 대해서 최소 공배수와 최대 공약수는 a * b === GCD * LCM 관계가 성립한다.
따라서, 최소 공배수a * b / GCD를 사용해 구할 수 있다.

예시 문제

두 수를 입력받아 두 수의 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM)를 담은 배열을 반환하는 함수를 만드는 문제를 통해 유클리드 호제법을 직접 실습해볼 수 있다.
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; }
JavaScript

출처