[Algorithm] 유클리드 호제법

Algorithm in HelloMinchan

[Algorithm] 유클리드 호제법

(글쓴날 : 2020.03.23)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

유클리드 호제법

---

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

유클리드 호제법이란 어떤 두 자연수의 최대공약수를 구하는 알고리즘의 하나로 최대공약수를 구하는 알고리즘 중 가장 대표적인 알고리즘입니다.

호제법이란 주어진 두 수로 서로 다른 수를 나누어 원하는 결과를 얻는 방법을 의미하며,

그에 따라, 유클리드 호제법은

 

어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

 

라는 성질을 이용한 알고리즘입니다.

 

위의 원리에 따라, a를 b로 나눈 나머지를 다시 a로 사용하고 b로 또 나누고 이렇게 반복하다, 나누어떨어질 때 나눈 수가 바로 두 수의 최대공약수가 됩니다.

---

2) 코드

코드는 재귀를 사용하면 매우 간단합니다.

gcd는 영어로 최대공약수 greatest common divisor의 약자이며, 함수화된 코드입니다.

gcd() 함수에 두 자연수를 인자로 넘겨주시면 최대공약수가 반환됩니다.

 

* Python 코드

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
 
최대공약수 = gcd(자연수1, 자연수2)

---