안녕하세요!
이번에는 수학 알고리즘 중 최대공약수, 최소공배수를 구할 때 활용할 수 있는 '유클리드 호제법'에 대해서 정리해보려고 합니다 :)
알고리즘이 수학과 관련이 높은 만큼 종종 접하는 문제 유형인 듯 합니다.
수학 알고리즘이 생각보다 정수론이나 특정 이론과 관련있는 경우가 많아서인지,
수학 공부를 하지 않은 상태에서는 떠올리기가 쉽지 않은 경우도 종종 있습니다.
이렇게 문제 풀면서 정리해보는 것도 좋을 듯 하여,
수학 알고리즘 중 하나인 '유클리드 호제법'도 정리해봅니다 !!
유클리드 호제법 Euclidean Algorithm
유클리드 호제법은
두 수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 으로,
나눗셈을 반복해 계산하며 최대공약수를 찾습니다.
< 유클리드 호제법 >
두 수 a, b (단, a ≥ b)의 최대공약수 구하기
1. a를 b로 나눈 나머지 r을 구한다.
: r = a mod b
2. a를 b로 바꾸고, b를 r로 변경한다. (반복)
: a ← b, b ← r
3. b = 0이 되면, 이 때의 a가 최대공약수(GCD)
: b = 0, gcd = a
즉,
"큰 수를 작은 수로 나눈 나머지를 계속 구하다 보면, 결국 최대공약수를 얻게 된다."
를 알 수 있습니다.
참고로,
◆ 유클리드 호제법에서 나머지가 공약수를 유지하는 이유 ◆에 대해서도 추가로 정리해보면 아래와 같습니다.
1. 최대공약수(GCD)의 정의
두 수 a와 b의 최대공약수를 d라고 하겠습니다.
즉,
이 뜻은,
a와 b는 모두 d의 배수
a=dx,b=dy(어떤 정수 x,y 가 존재함) 라고 할 수 있습니다.
2. 유클리드 호제법에서 몫과 나머지
유클리드 호제법에서는 나머지 r를 사용하여 GCD를 구합니다.
즉, 다음과 같이 나눗셈을 수행합니다.
a = bq + r
(여기서 는 몫, 은 나머지)
3. 나머지 r도 d의 배수임을 증명
위 식을 조금 변형해보겠습니다.
r = a - bq
여기서, a와 b는 모두 d의 배수이므로 a=dx,b=dy 를 대입하면,
r=dx
공통 인수 d를 묶어주면,
r=d(x−yq)
즉, 도 의 배수입니다!
4. 결론
- 즉, gcd(a,b)=gcd(b,r)이 성립합니다.
- 나머지 도 최대공약수 를 유지한 채 줄어듭니다.
- 반복하면 결국 b=0이 되고, 그때 남은 a가 최대공약수입니다.
정리: 유클리드 호제법의 핵심 요약
- 유클리드 호제법은 단순한 반복이 아닌 수학적 공약수 성질을 보존하는 원리를 이용합니다.
- 그래서 정수론, 수론, 암호학 등에서도 자주 사용됩니다.
| 특징 | 내용 |
| 개념 | 두 수를 나누고 나머지를 계속 구하면서 GCD 찾기 |
| 시간복잡도 | O(log N) (매우 빠름) |
| 장점 | 간단한 구현, 빠른 속도 |
| 코드 구현 | 재귀 / 반복문 가능 |
| 확장 가능 | 확장 유클리드 알고리즘으로 해(x, y)도 구할 수 있음 |
유클리드 호제법(Euclidean Algorithm) 수학적 증명
이렇게 공부하니 그 다음으로 궁금한 건 수학적 증명이었습니다.
수학적 증명을 확인해보면 알고리즘 동작이 더 잘 이해될 것 같았습니다.
유클리드 호제법을 수학적으로 증명한다면 아래와 같습니다.
유클리드 호제법을 간단히 나타내면 이렇게 나타낼 수 있는데요,
a = b * q + r
→ gcd(a, b) = gcd(b, r)이를 바탕으로 수학적 증명을 진행해보겠습니다.
목표: 왜 인가?
◆ 기본 성질 증명
두 정수 a, b (a ≥ b)의 최대공약수를 d라고 해봅니다.
gcd(a, b) = d라고 할 때,
a와 b는 모두 d의 배수이므로 다음을 만족합니다.
a = dx, b = dy (단, x, y 는 정수)
유클리드 호제법에서는 a를 b로 나눈 나머지 r을 사용합니다.
즉,
a = bq + r (q는 몫, r은 나머지)
이 때, r도 d의 배수임을 보일 수 있습니다.
◆ 유클리드 호제법 공약수 유지 성질 증명
위의 식에서 a, b를 대입하면,
d * a' = q * d * b' + r이고, 정리하면 아래와 같습니다.
d * a' = d * b' * q + r
이제 양 변에서 d를 묶어보면
d * a' = d * (b' * q) + r
=> r = d * (a' - b' * q)
와 같이 나타낼 수 있으며, 나머지 r도 d의 배수임을 알 수 있습니다.
참고로, (a'-b'*q)도 정수이므로 r*d도 정수입니다.
r = d * 정수
따라서
gcd(a, b) = gcd(b, r)이므로
1. GCD는 변하지 않는다
2. 따라서 반복적으로 나머지를 구해도 최대공약수는 유지된다
라는 결론을 얻을 수 있습니다.
◆ 유클리드 호제법이 반드시 종료되는 이유
유클리드 호제법 과정:
gcd(a, b) = gcd(b, a mod b)여기서 매 단계마다 a, b는 작아집니다.
즉,
b > a mod b > (a mod b) mod b > ...이런 방식으로 줄어들다가 결국 b = 0이 되면 a가 최대공약수로 남습니다.
따라서,
수학적으로도 항상 종료됨이 보장됩니다.
유클리드 호제법(Euclidean Algorithm) 구현 예시(Java)
유클리드 호제법 구현은 어렵지 않습니다.
계속 나머지를 구하는 연산을 반복해나갑니다.
재귀함수로 구현하는 방법과 반복문으로 구현하는 방법 모두 예시를 첨부하였습니다 :)
각 예시에는 main에서 a, b를 임의로 정하여 호출하는 로직도 첨부하였습니다!
재귀함수 구현
public class GCDRecursive {
public static int gcd(int a, int b) {
if (b == 0) return a; // 종료 조건
return gcd(b, a % b); // 재귀 호출
}
public static void main(String[] args) {
int a = 252, b = 198;
System.out.println("GCD: " + gcd(a, b)); // 출력: 18
}
}
반복문 구현 예시
public class GCDIterative {
public static int gcd(int a, int b) {
while (b != 0) { // b가 0이 될 때까지 반복
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
int a = 252, b = 198;
System.out.println("GCD: " + gcd(a, b)); // 출력: 18
}
}유클리드 호제법(Euclidean Algorithm) 시간 복잡도
유클리드 호제법의 시간복잡도도 확인해보겠습니다.
유클리드 호제법의 시간복잡도는 O(log N) 입니다.
- 각 단계에서 의 값이 거의 절반 이하로 감소합니다.
각 단계마다
a mod b
즉, a % b (나머지 연산)
를 수행하면서 값이 빠르게 작아집니다.
- 최대 O 단계 내에 연산이 종료됩니다.
최악의 경우 피보나치 수열처럼 작아져도 약 만큼의 반복으로 충분합니다.
- 즉, a와 가 자리 수일 때, 연산 횟수는 대략 만큼 걸립니다.
✔ 굉장히 빠른 알고리즘으로, 매우 큰 수의 최대공약수도 빠르게 구할 수 있습니다!
유클리드 호제법(Euclidean Algorithm) 확장 - 최소공배수 구하기
두 수의 최소공배수(Least Common Multiple)란,
두 수의 공통 배수 중에서 가장 작은 양의 수 이다.
최대공약수(gcd)와 최소공배수(lcm)의 관계는 아래와 같습니다.
LCM(a, b) = a * b / GCD(a, b)
식이 성립하는 이유는 아래와 같습니다.
1. a x b는 a와 b의 공통으로 나누는 최대공약수가 중복되어있다.
2. 따라서 그 중복을 제거하기 위해 gcd(a, b)로 나누는 것
최소공배수와 최대공약수의 관계성에 대해 수학적 증명도 정리해보겠습니다.
a * b = gcd(a, b) * lcm(a, b)
조건
1. a, b는 양의 정수
2. d = gcd(a, b)
3. m = lcm(a, b)
라고 하겠습니다.
먼저 a, b는 공약수 d를 가지므로 각자 아래와 같이 나타낼 수 있습니다.
1. a = d * a'
2. b = d * b'
이 때, 최대공약수는 d이므로 a', b'는 서로소(공약수가 1)입니다.
즉, gcd(a', b') = 1 입니다.
위 1, 2의 양 변을 곱합니다.
(d^2는 d의 2제곱을 뜻합니다.)
a * b = d * a' * d * b' = d^2 * a' * b'
이번에는 최소공배수를 식으로 보겠습니다.
lcm(a', b') = a' * b'
gcd(a', b') = 1 이므로 a', b'의 최소공배수는 두 수의 단순 곱 입니다.
그렇다면 a, b의 최소공배수는
lcm(a, b) = d * lcm(a', b') = d * a' * b'
결론적으로
a * b = d^2 * a' * b'
gcd(a, b) = d
lcm(a, b) = d * a' * b'
입니다.
곱해보면
gcd(a, b) * lcm(a, b) = d * (d * a' * b') = d^2 * a' * b' = a * b
따라서
a * b = gcd(a, b) * lcm(a, b)
가 됩니다.
예제 문제 풀이: BOJ 2609 최대공약수와 최소공배수
* 예제 문제: BOJ 2609 최대공약수와 최소공배수
링크: https://www.acmicpc.net/problem/2609
문제:
두 개의 자연수에 대해 최대공약수와 최소공배수를 구하는 문제입니다.
example:
24 18
최대공약수는 유클리드 호제법을 생각하며 나눗셈을 진행한다면 아래 표와 같이 진행됩니다.
| a | b | 나머지 r |
| 24 | 18 | 6 |
| 18 | 6 | 0 |
| 6 | 0 |
따라서 최대공약수는 6입니다.
최소공배수는 위 '유클리드 호제법(Euclidean Algorithm) 확장 - 최소공배수 구하기' 에서 확인할 수 있듯이,
a * b 한 결과를 gcd(a, b), 즉 a 와 b의 최대공약수로 나누면 구할 수 있습니다.
lcm(a, b) = (a * b) / gcd(a, b)
로 계산하면 됩니다.
최대공약수(gcd), 최소공배수(lcm)을 구하는 함수 구현은 아래와 같습니다.
// 최대공약수
public static int gcd(int a, int b) {
if(b==0) return a;
return gcd(b, a % b);
}
// 최소공배수
public static int lcm(int a, int b) {
return a*b/gcd(a, b);
}원리와 식만 알면 간단히 풀 수 있습니다 !
아래 캡쳐본도 첨부합니다 :)
수학 알고리즘은 공부하기 전까지 잘 생각이 나지 않는 경우가 종종 있는데요,
이런 기회에 정리하고 가는 것도 참 좋은 듯 합니다.
정리가 잘 되면 그래도 잘 떠오르더라고요 ㅎㅎ
나중에 어려운 알고리즘 문제에서 활용을 잘 할 수 있길 바라며,,
확장 유클리드 호제법도 추후 포스팅해보려고 합니다!
그럼 이번 정리도 도움이 많이 되었길 바라며 포스팅을 마칩니다 :)
