🔧변경내용🔨

제목	날짜	내용
발행일	23.04.06

📌들어가기에 앞서

해당 포스트는 최대공약수와 최소공배수를 학습한 것을 정리한 내용입니다.

---

🌈 GCD

최대공약수(Greatest Common Divisor, GCD)는 두 수 이상의 여러 공약수 중 최대인 수를 가리킨다.

공약수(Common Divisor)

최대공약수의 개념 중 공약수는 두 수 이상의 여러 수 중 공통된 약수를 의미한다.

약수(Divisor)는 어떤 수를 나누어떨어지게 하는 수를 의미한다.

여기 6과 9 두 수가 있다. 미리 표기한 것처럼 6의 약수는 1, 2, 3, 6이고 9의 약수는 1, 3, 9다. 이 중 공통된 약수는 1, 3으로 공약수라고 표현한다.

여기서 최대공약수를 찾아보자.

여러 개의 공약수 중 최대인 수가 바로 최대공약수이므로, 6과 9의 최대공약수는 3이다.

---

🌈 LCM

최소공배수(Lowest Common Multiple, LCM)는 두 수 이상의 여러 공배수 중 최소인 수를 가리킨다.

공배수(Common Multiple)

최소공배수의 개념 중 공배수는 두 수 이상의 여러 수 중 공통된 배수를 의미한다.

여기서 배수(Multiple)는 하나의 수에 정수를 곱한 수다.

반대로 말해서, 배수는 그 수에 의해 나누어 떨어지는 수라고 볼 수 있다.

12와 18 두 수가 있다.

두 수의 공배수는 이런 식으로 해당 수의 배수를 나열해 겹치는 수를 찾는 방식으로 구할 수 있다.

공배수의 경우 배수이기 때문에 무수히 많으므로 가장 큰 공배수는 구할 수 없다.

그러므로 최소공배수를 찾아야 하는데, 여기서 최소 공배수는 36이다.

---

💻 GCD와 LCM을 구하는 방식

구하는 방식에는 여러 방식이 있다.

가장 작은 수들의 곱으로 나타내며 구하는 방식과, 공약수로 나누어보며 최대공약수와 최소공배수를 구하는 방법이 있다. 그리고 마지막에는 알고리즘 문제에서 가장 많이 쓰이는 유클리드 호제법을 알아보도록 하자.

가장 작은 수들의 곱으로 나타내며 구하는 법

여기 다시 12와 18이 있다.

12와 18을 가장 작은 수의 곱으로 나타내보자.

여기서 겹치는 부분인 2와 3을 곱한 수인 6이 최대공약수고,

6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수가 된다.

공약수로 나누어보며 구하는 법

이번에는 공약수로 나누어보며 최대공약수와 최소공배수를 구하는 법을 알아보자.

우리는 이미 2와 3이 공약수임을 알고 있다.

해당 공약수들로 12와 18을 더 이상 나눌 수 없는 수까지 나눕니다.

여기서 나누는 데에 사용된 수인 2와 3을 곱하면 6이 나오고, 이 6은 최대공약수가 된다.

나누는 데에 사용된 수와 더 이상 나눌 수 없는 수들을 곱하게 되면 36이 나오고, 이 수는 최소공배수가 된다.

유클리드 호제법

GCD와 LCM 개념이 쓰이는 문제를 풀 때 가장 많이 쓰이는 유클리드 호제법에 대해 알아보도록 하자.

유클리드 호제법을 알고 있다면 최대공약수와 최소공배수를 구하는 모든 문제에 일단 적용해보고 시작할 수 있게 된다.

유클리드 호제법은 최대공약수와 관련이 깊은 공식이다.

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면,

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론이다.

이러한 성질에 따라

• b를 r로 나눈 나머지 r’를 구하고,
• 다시 r을 r’로 나누는 과정을 반복해,
• 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대공약수임을 알 수 있게 된다.

해당 수식을 보며 다시 이해해보도록 하자.

여기 2개의 자연수 a와 b가 있습니다.

단 a가 b보다 커야 한다는 조건(절대적 조건)이 있다.

왜냐하면 나누었을 때 음수가 나오면 안 되기 때문이다.

이제 a와 b를 나누었을 때 q와 r이 나옵니다.

q는 몫(Quotient)을 의미하고, r은 나머지(Rest)를 의미한다.

여기서 다시 b를 r로 나눕니다.

그러면 다시 몫인 q와 나머지인 r’가 나올 것이고,

r을 다시 r’와 나누게 되면 언젠가 몫인 q의 값과 나머지인 r이 0이 되는 상황이 도출된다.

이때 나누는 수인 r’가 바로 최대공약수라는 의미다.

이번에는 실제 자연수를 이용해 확인해보자.

81과 15가 있다.

같은 방식으로 쭉 나눴을 때, 마지막 나눗셈에서 나누는 수인 3이 최대공약수임을 확인할 수 있다.

이런 식으로 유클리드 호제법을 이용하게 되면 최대공약수를 쉽게 구할 수 있게 되고, 최대공약수를 구할 수 있게 되면 최소공배수는 자연스럽게 구할 수 있다.

---

💻 javascript code

GCD

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

해당 함수 gcd 는 유클리드 호제법을 적용한 로직이다.

함수 선언을 한 뒤 a와 b를 매개변수로 받고 있으며, 그 안에 while문으로 이루어진 중심 로직이 있다.

while문은 b는 0이 아니어야 함을 조건으로 받고 있는데, 왜 0이 아니어야 하냐면 모든 자연수를 0으로 나누게 되면 리턴되는 값이 Infinity이기 때문이다.

값이 무한대로 나오면 안 되기 때문에 해당 조건을 걸어둠으로써 값이 제대로 나오지 않는 상황을 방지한다.

해당 조건을 지키며 b가 0이 될 때까지 계속 while문은 돌아간다.

변수 r 은 a와 b의 나머지가 할당
a는 b로 재할당
b는 r로 재할당

마지막으로 리턴하는 값은 a로, 이 a를 리턴하는 이유는 while문이 돌아가면서 나누는 수를 재할당을 하기 때문

GCD 다른 버전

function gcd(a, b) { // 단, a가 b보다 커야함.
  let r;
  while ((a % b) > 0)  {
    r = a % b;
    a = b;
    b = r;
  }
  return b;
}

function gcd(a, b) { // 단, a가 b보다 커야함.
  if (b == 0)
    return a;
  else
    return gcd(b, (a % b));
}

function gcd(a,b) {return b ? gcd(b,a%b) : Math.abs(a)}

LCM

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

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

해당 함수 lcm 은 마찬가지로 a와 b를 매개변수로 받고 있으며, 리턴되는 값으로 a에 b를 최대공약수로 나눈 값을 곱하고 있다.

여기서 최대공약수의 값은 위에서 만들었던 함수 gcd를 이용해 구할 수 있다.

최소공배수는 최대공약수를 이용해서 만들어지는 수다.

그러므로 최대공약수를 만들 줄 알면 최소공배수 또한 만들 수 있게 된다.

function gcd(a,b) {return b ? gcd(b,a%b) : Math.abs(a)}

function solution(n, m) {

  let a = n > m ? n : m
  let b = n < m ? n : m
  let k = gcd(a,b)

  return [k, a*b/k]
})

---

🥊 GCD와 LCM을 이용한 문제들

시작하기 전에 기억해두어야 할 용어

• 약수: 어떤 수를 나누어떨어지게 하는 수

• 배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수

• 공약수: 둘 이상의 수의 공통인 약수

• 공배수: 둘 이상의 수의 공통인 배수

• 최대공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수

• 최소공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

문제: Mask States

방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요?
(휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

풀이 방법은 다양히다. 그러나 이 문제에서 최소 공배수를 떠올릴 수 있다면, 더 쉽고 빠르게 문제를 해결할 수 있다.

	작업 시간 + 쉬는 시간 5분
A	60분에 9개
B	75분에 15개
C	90분에 25개

세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 된다.

따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로, 앞서 학습했던 최소공배수의 개념을 알아야 한다.

결과적으로, LCM(60, 75, 90)은 900이다. (LCM; Least Common Multiple, 최소 공배수)

• A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 900/60 = 15 번 작업하고, 15번 X 9개 = 135개의 마스크를 만든다.
• B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개,
• C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 만든다.

따라서, A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개가 된다.

최소공배수를 쉽게 알아내는 법은 앞서 소개한 유클리드 호제법을 사용하는 것이다.

---

📚 레퍼런스

유클리드 호제법의 원리