유클리드 호제법
1. “호제”가 뭔데?
호제법은 한자로 보면 互除法이다.
- 互 = 서로
- 除 = 나누다
- 法 = 방법
즉, 서로 나누는 방법이라는 뜻이다.
그래서 유클리드 호제법은 쉽게 말하면,
두 수를 서로 나눠가면서 최대공약수(GCD) 를 구하는 방법이다.
GCD : Greatest Common Divisor
2. 최대공약수란?
최대공약수는 말 그대로
두 수가 공통으로 가지고 있는 약수 중에서 가장 큰 수를 말한다.
예를 들어 12와 18이 있다고 해보자.
12의 약수
1, 2, 3, 4, 6, 12
18의 약수
1, 2, 3, 6, 9, 18
공통 약수
1, 2, 3, 6
여기서 가장 큰 수는 6이다.
따라서,
gcd(12, 18) = 6
이 된다.
3. 유클리드 호제법의 핵심
유클리드 호제법의 핵심은 이 공식이다.
gcd(a, b) = gcd(b, a % b)
두 수
a,b의 최대공약수는
b와a를 b로 나눈 나머지의 최대공약수와 같다.
gcd(a, b) = gcd(a, a % b) 는 성립하지 않는다.
4. 예시: 48과 18의 최대공약수
48과 18의 최대공약수를 구한다고 해보자.
처음에는 이렇게 시작한다.
gcd(48, 18)
먼저 48을 18로 나눈다.
48 / 18 = 2 ... 12
나머지가 12다.
그러면 원래 문제를 이렇게 바꿀 수 있다.
gcd(48, 18) = gcd(18, 12)
이제 18을 12로 나눈다.
18 / 12 = 1 ... 6
나머지가 6이다.
그러면 다시 이렇게 바꿀 수 있다.
gcd(18, 12) = gcd(12, 6)
이제 12를 6으로 나눈다.
12 / 6 = 2 ... 0
나머지가 0이다.
나머지가 0이 되는 순간,
그때의 나누는 수가 최대공약수다.
따라서,
gcd(48, 18) = 6
이 된다.
5. 흐름만 보면
gcd(48, 18)
→ gcd(18, 12)
→ gcd(12, 6)
→ gcd(6, 0)
→ answer = 6
즉, 계속 이렇게 바뀌는 것이다.
- 큰 수, 작은 수
- 작은 수, 나머지
- 작은 수, 나머지
- 나머지가
0이 될 때까지 반복
6. JS 코드
아래처럼 구현할 수 있다.
function gcd(a, b) {
while (b !== 0) {
let rest = a % b;
a = b;
b = rest;
}
return a;
}파이썬 코드
def gcd(a, b):
while b != 0:
rest = a % b
a = b
b = rest
return a반복문을 따라가면 이렇게 된다.
a, b = 48, 18
rest = 12
a = 18
b = 12
a, b = 18, 12
rest = 6
a = 12
b = 6
a, b = 12, 6
reset = 0
a = 6
b = 0 // b가 0이 됐으니 반복문 탈출
return a = 6
gcd(48,18) = 6최소공배수
1. 최소공배수란?
최소공배수는 말 그대로
두 수가 공통으로 가지는 배수 중에서 가장 작은 수다.
LCM : Least Common Multiple
예를 들어 48과 18의 최소공배수는
두 수가 동시에 나누어 떨어지는 가장 작은 수를 찾는 것이다.
2. 최소공배수 공식
최소공배수는 최대공약수를 이용해서 구할 수 있다.
lcm(a, b) = (a * b) / gcd(a, b)
즉,
두 수를 곱한 다음
최대공약수로 나누면
최소공배수가 나온다.
3. 왜 최대공약수로 나누는 거야?
두 수를 그냥 곱하면
두 수가 공통으로 가지고 있는 부분이 중복해서 들어간다.
예를 들어 48과 18을 보자.
두 수의 최대공약수는 6이다.
48 = 6 * 8
18 = 6 * 3
여기서 6은 두 수가 공통으로 가지고 있는 부분이다.
그런데 두 수를 그냥 곱하면,
48 * 18
은 이렇게 볼 수 있다.
(6 * 8) * (6 * 3)
즉,
6 * 8 * 6 * 3
공통 부분인 6이 두 번 들어간다.
하지만 최소공배수에서는 공통 부분을 한 번만 가져가면 된다.
그래서 한 번 중복된 6을 나눠준다.
(48 * 18) / 6
= 864 / 6
= 144
따라서,
lcm(48, 18) = 144
가 된다.
Python 같은 경우 math 라이브러리에 gcd 메소드를 쓰면 간단하게 최대공약수,최소공배수를 구할 수 있지만 JS는 내장 메소드가 없기 때문에 이렇게 유클리드 호제법 공식을 기억이라도 하고 있어야 수월하게 최대공약수, 최소공배수를 구할 수 있다.
