최대공약수와 유클리드 호제법
최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나누어떨어지게 하는 가장 큰 수입니다. 약수를 일일이 구해 비교하지 않고, 유클리드 호제법(Euclidean algorithm)으로 O(log)에 빠르게 구합니다. 최소공배수(LCM)는 GCD만 알면 바로 계산됩니다.
핵심 한 줄: "큰 수를 나머지로 바꿔 가며 줄인다." 두 수가 나머지 연산으로 점점 작아지고, 나머지가 0이 되는 순간이 답입니다.
핵심 성질
gcd(a, b) = gcd(b, a mod b)
즉 a를 b로 나눈 나머지로 문제를 줄여, b가 0이 되면 그때의 a가 최대공약수입니다.
왜 성립하나? a = q·b + r로 쓰면, a와 b의 공약수는 정확히 b와 r(= a mod b)의 공약수와 같습니다(어느 한쪽을 나누면 다른 쪽도 나눔). 그래서 두 수를 (b, a mod b)로 바꿔도 최대공약수가 보존됩니다.
동작 원리
1단계. b가 0이면 a가 최대공약수입니다(종료).
2단계. 아니면 gcd(b, a mod b)로 줄여 재귀(또는 반복)합니다.
3단계. 나머지가 0이 될 때까지 반복하면, 나누는 수가 GCD로 남습니다.
알고노트 시각화는 두 수가 나머지 연산으로 어떻게 줄어드는지 단계별로 보여줍니다.
LCM은 GCD로
lcm(a, b) = a / gcd(a, b) × b
전체 곱 a × b를 GCD로 나눈 값입니다. 단, a × b를 먼저 곱하면 큰 수에서 오버플로가 날 수 있으니 a / gcd × b 순서로 먼저 나눈 뒤 곱하는 것이 안전합니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(log(min(a, b))) |
| 공간 | O(1) (반복 구현) |
나머지 연산이 매 단계에서 값을 빠르게 줄이므로 로그 시간입니다.
예시로 따라가기
gcd(48, 18):
- •gcd(48, 18) → 48 mod 18 = 12 → gcd(18, 12)
- •gcd(18, 12) → 18 mod 12 = 6 → gcd(12, 6)
- •gcd(12, 6) → 12 mod 6 = 0 → gcd(6, 0) = 6
따라서 GCD는 6, lcm(48,18) = 48 / 6 × 18 = 144입니다.
자주 하는 실수
- •LCM 오버플로:
a × b를 먼저 곱하면 자료형 범위를 넘을 수 있습니다. 나눗셈을 먼저 하세요. - •0 처리:
gcd(a, 0) = a규칙을 빠뜨리면 종료 조건이 깨집니다. - •음수 입력: 보통 절댓값을 취해 다룹니다.
알고노트에서 직접 확인하세요
큰 수가 나머지 연산으로 작아지며 최대공약수에 도달하는 과정을 알고노트에서 단계별로 확인할 수 있습니다.