유클리드 호제법(Euclidean Algorithm) 이란 무엇인가

1. 유클리드 호제법이란?

유클리드 호제법은 두 정수의 최대공약수(GCD) 를 구하는 가장 효율적인 알고리즘이다.

약수를 직접 나열하지 않고, 나눗셈의 나머지를 이용해 최대공약수를 구한다.

---

2. 핵심 아이디어 한 줄 요약

두 수 a, b의 최대공약수는
b와 a % b의 최대공약수와 같다.

수식으로 표현하면

gcd(a, b) = gcd(b, a % b)

---

3. 왜 이 방법이 성립할까?

다음과 같이 나눗셈을 생각해보자.

 

a = b × q + r (r = a % b)

어떤 수 d가

• a를 나누고
• b를 나눈다면

a - b × q 도 반드시 나눈다.

그런데

a - b ×q= r

즉,

a와 b의 공약수 = b와 r의 공약수

이 성질 때문에
(a, b)를 (b, a % b)로 바꿔도
최대공약수는 변하지 않는다.

---

4. 알고리즘 진행 과정 (예시)

예시: gcd(18, 12)

1. 18 % 12 = 6
   → gcd(18, 12) = gcd(12, 6)
2. 12 % 6 = 0
   → 나머지가 0이므로 종료

📌 최대공약수 = 6

---

5. 알고리즘 절차 정리

1. 두 수 a, b를 준비한다
2. a % b를 계산한다
3. 나머지가 0이면 b가 최대공약수
4. 아니면 (b, a % b)로 다시 반복

나머지는 점점 작아지기 때문에
반드시 종료한다.

---

6. 특징과 장점

• 약수 나열 ❌
• 소인수분해 ❌
• 시간복잡도: O(log N)
• 큰 수에도 매우 빠름

그래서:

• 코딩 테스트
• 알고리즘 문제
• 프로그래밍 언어 내장 함수

에서 기본적으로 사용된다.

---

7. 최소공배수(LCM)와의 관계

유클리드 호제법으로 GCD를 구하면
LCM은 다음 공식으로 바로 구할 수 있다.

LCM(a,b)=(a × b)/GCD(a,b)

즉,

• 최소공배수 문제도
• 결국 유클리드 호제법이 핵심

---

8. 정리

• 유클리드 호제법은 최대공약수를 구하는 알고리즘
• 나머지를 이용해 문제 크기를 줄여나감
• gcd(a, b) = gcd(b, a % b)
• 최소공배수 문제에도 그대로 활용 가능

👉 GCD / LCM 문제가 보이면 가장 먼저 떠올려야 할 알고리즘