유클리드 호제법(Euclidean algorithm)

‣ 유클리드 호제법

유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘으로,

두 수의 최대공약수를 구하는 알고리즘이다.

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 것으로, 서로 호(互)와 덜(나누기) 제(除)를 써서 호제법이다.

---

‣ 예시: 1071과 1029의 최대공약수 계산하기

[일반적인 방법]

일반적으로 최대공약수를 구한다고 생각한다면, 먼저 소인수분해를 떠올린다.

1071 = 17 x 7 x 3 x 3

1029 = 7 x 7 x 7 x 3

두 수를 소인수분해한 결과, 공통된 소수를 찾으면 된다.

이를 통해 두 수의 최대공약수(GCD)가 " 7 x 3 = 21 "인 것을 알 수 있다.

 

하지만, 이 방법은 수가 커질 수록, 소인수분해를 수행하기 어려워진다는 단점이 있다.

유클리드 호제법은, 이러한 단점을 보완해 더 효율적으로 최대공약수(GCD)를 구할 수 있는 방법이다.

---

[유클리드 호제법을 사용한 방법]

유클리드 호제법은 두 값을 나눈 나머지를 구하는 MOD연산이다.

 

먼저, 큰 수를 작은 수로 나눈 나머지를 구한다.(= MOD연산)

1071 mod 1029 = 42

// 아래 식이랑 같습니다.
1071 % 1029 = 42

 다음으로, 나눴던 수와 나머지로 또 MOD 연산을 진행한다.

1029 mod 42 = 21
// 1029 % 42 = 21

이 과정을 계속 반복하여 나머지가 0이 되었을 때, 마지막 계산에서 나누는 수로 사용된 수가 최대 공약수(GCD)가 된다.

42 mod 21 = 0
// 42 % 21 = 0
// GCD == 21

 

∴ 유클리드 호제법은 MOD연산 (%)을 계속 반복하면 된다.

---

‣ 그림으로 보기

유클리드 호제법 gif

앞으로 다시는 안만들 ppt 애니메이션.

---

‣ 요약

유클리드 호제법은 나눗셈만 반복해서 최대공약수(GCD)를 구할 수 있다.

두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다.

---

‣ 코드

[Python]

def Euclidean(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

📎 def를 쓰지 않고 좀 더 간결하게 표현한다면??

while (b):
    a, b = b, a%b

 

[Kotlin]

fun Euclidean(num1:Int, num2:Int):Int{
    var r:Int = 0
    var a:Int = num1
    var b:Int = num2
    while(b!=0){
        r=a%b
        a=b
        b=r
    }
    return a
}

---

‣ 유클리드 호재법 관련 백준 문제

• 2609번: https://www.acmicpc.net/problem/2609
• 13241번: https://www.acmicpc.net/problem/13241
• 3036번: https://www.acmicpc.net/problem/3036
• 2942번: https://www.acmicpc.net/problem/2942

---

‣ Reference

유클리드 호제법 - 위키백과, 우리 모두의 백과사전