[Algorithms] 유클리드 호제법 - 최대공약수와 최소공배수

코딩테스트 문제를 풀면서 코드 한줄이라도 맞으면서 배우자는 마인드를 가지고 있었다.

하지만, 최대공약수 문제를 마주할 때 마다 유클리드 호제법을 알고 작성한 코드와 모르고 작성한 코드는 확연한 차이를 보이는 걸 알 수 있었다.

남들보다 for, if문을 불필요하게 많이 작성했던 지난 날의 코드를 반성하며 유클리드 호제법에 대해 알아보자.

유클리드 호제법이란?

💡

유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘.
두 수의 최대공약수를 구하는 알고리즘. 최대공약수를 안다면 최대공배수도 쉽게 구할 수 있다.

 

 

최대공약수 (Greatest Common Divisor, GCD)

• 두 수가 공통적으로 가지고 있는 약수 중 가장 큰 수

최소공배수 (Lowest Common Multiple, LCM)

• 두 수가 공통적으로 가지고 있는 가장 작은 배수

 

---

유클리드 호제법을 왜 알아야 할까?

일반적으로 수학문제를 풀 때 약수는 나누기를 반복하여 구할 수 있다.

for, if문을 활용해 구현할 수는 있지만 숫자가 커진다면 그만큼 연산도 많아지기 마련이다.

하지만 유클리드 호제법을 사용하면 효율적으로 최대공약수를 구할 수 있다.

 

 

유클리드 호제법

• 두 수 a, b를 서로 나눌 때, 나누어지면 b가 최대공약수이다. (a > b)
• 만약 a, b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다.
• b와 a%b가 나누어 진다면 a%b가 최대공약수이다. 
• 위 연산을 두 수가 나머지수 없이 나누어질 때 까지 반복하여 최대공약수를 구한다.

 

 

위 조건을 코드로 작성하면 아래와 같은 코드가 작성된다.

 

GCD 최대공약수

function gcd(a, b) {
	let max = Math.max(a,b);
    	let min = Math.min(a,b);
    
	return max % min === 0 ? min : gcd(min, max % min);
}

 

LCM 최소공배수

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

 

삼항연산자와 재귀함수를 활용해 짧은 코드로 작성할 수 있다.

최소공배수는 최대공약수를 안다면 두 수의 곱을 최대공약수로 나눠서 얻을 수 있다.

 

 

 

참조

- https://rebornbb.tistory.com/entry/JS-Programmers-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%E2%98%91
- https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95