[python] 재귀호출로 최대공약수 구하기 - 유클리드 호제법 이용

 

 

재귀호출로 최대공약수 구하기 - 유클리드 호제법 이용

 

유클리드 호제법은 최대공약수를 구하는 알고리즘 중의 하나이다.

* 최대공약수 GCD, greatest common divisor

 

 

위키백과 <유클리드 호제법> 참고

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 

 

유클리드 호제법을 간단히 설명하자면

gcd(x, y) 라는 함수는 x와 y의 최대공약수를 구하는 함수라고 하자. 그러면 gcd(x, y) = gcd(y, x % y) 가 성립하게 된다는 알고리즘이다.

 

예를 들어 36, 20 두 숫자의 최대공약수를 구한다고 하자.

 

gcd(36, 20) = gcd(20, 16) = gcd(16, 4) 

 

여기서 16은 4로 나누어 떨어지므로(나머지가 0이므로) 최대공약수는 4가 된다.

 

 

---

 

 

두 정수를 입력받아 두 수의 최대공약수를 출력하는 프로그램을 작성해보자.

(두 정수는 띄어쓰기로 구분하여 입력한다.)

 

def mygcd(x, y) : # 최대공약수를 구하는 함수
    
    if x%y == 0 : # 기저 조건 설정
        return y
    
    return(mygcd(y, x % y))
    

data = input() # 입력을 받으면 리스트로 저장함

x = int(data.split()[0])
y = int(data.split()[1])

print(mygcd(x, y))

 

 

유클리드 호제법을 식으로 표현하여 mygcd 라는 최대공약수를 구하는 함수를 정의하였다.

재귀함수를 사용할 때는 기저조건이 필요하니, x % y 연산이 0이 되면, y를 반환하는 것으로 하여

유클리드 호제법으로 최대공약수를 구하는 코드를 완성하였다.

 

입력 :

36 20

 

출력 :

4

 

로 잘 출력되는것을 확인할 수 있다.