[230321] 최대공약수(GCD), 최소공배수(LCM)

 

 

최대공약수(GCD)

• 두 수 A와 B의 공통된 약수 중 가장 큰 정수
• 가장 쉬운 방법: 2부터 min(A,B)까지 모든 정수로 나눴을 때 나머지 값이 0인지 보기 (A % GCD)

const getGCD = (num1, num2) => {
	let gcd = 1;

	**for** (let i = 0; i <= Math.min(num1, num2); i++) {
		if (num1 % i === 0 && num2 % i === 0){
			gcd = i;
		}
	}
	return gcd;
}

 

 

최소공배수(LCM)

• 둘 이상의 수의 공통의 배수 중 가장 작은 수
• LCM을 1부터 시작하여 +1씩 더해가면서 LCM을 각 수로 나눴을 때 나머지 값이 0인지 보기 (LCM % A)

const getLCM = (num1, num2) => {
	let lcm = 1;

	**while** (true) {
		if (lcm % num1 === 0 && lcm % num2 === 0) {
			break;
		}
		lcm++;
	}
	return lcm;
}

 

 

유클리드 호제법을 이용한 구현

유클리드 호제법의 기본 원리

🧸 num1 % num 2 = r 라면,
     GCD(num1, num2) = GCD(num2, r) 이다.

따라서 r = 0 일 때, num2는 최대공약수이다.

 

(ex)

num1 = 24, num 2 = 16

GCD(24, 16) = GCD(16, 8) = GCD(8, 0)

따라서 GCD = 8.

 

재귀함수로 구현하기

const getGCD  = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

 

while문으로 구현하기

시간 복잡도는 O(logN) 이다.

const getGCD2 = (num1, num2) => {
	while(num2 > 0){
		const r = num1 % num2;
		num1 = num2;
		num2 = r;
	}
	return num1;
}

 

최대공약수(GCD)로 최소공배수(LCM) 구하기

• num1, num2의 최대공약수를 gcd라 했을 때, 최소공배수는 lcm = gcd * (num1/gcd) * (num2/gcd) 이다.
• 즉, num1 * num2 = gcd * lcm
• lcm = (num1 * num2) / gcd

 

유클리드 호제법 정리

function solution(num1, num2) {
	const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
	const lcm = (a, b) => a * b / gcd(a, b);
	
	return [gcd(num1, num2), lcm(num1, num2)];
}

 

---

피자 나눠 먹기(2)

프로그래머스

 

6과 n의 최소공배수를 찾는 문제이다. 최소공배수를 구하는 코드를 작성한 후, 나누기 6을 한 값을 반환하면 된다.

 

1. while문으로 풀기

function solution(n) {
	let lcm = 1;

	while(true){
		if((lcm % 6 === 0) && (lcm % n === 0)) {
			lcm++;
		}
	}
	return lcm / 6;
}

 

2. for 문으로 풀기

function solution(n) {
	let lcm = 1;

	for(let i = 0; (lcm % 6 !== 0) || (lcm % n !== 0); i++) {
		lcm++;
	}
	return lcm / 6;
}

 

 

3. 유클리드 호제법 활용하기

function solution(n) {
	const getGCD = (a, b) => a % b === 0 ? b : getGCD(b, a % b);
	const getLCM = (a, b) => a * b / getGCD(a, b);

	return getLCM(n, 6) / 6;
}

 

 

 

 

 

---

 

참고 자료

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기