파이썬 - 여러 수의 최대공약수 구하기

 여러 수의 최대 공약수를 구하기 위한 여러 가지 방법이 있겠지만!

 그중에서도 가장 효율적이라고 생각되는 유클리드 호제법에 대해 알아볼게!

 

 '유클리드 호제법 互除法' 또는 '유클리드 알고리즘 Euclidean algorithm'이란 두 자연수의 최대공약수를 구하는 알고리즘이야. 유클리드는 그 유명한 그리스의 수학자! 그분 맞아. 기원전 300년 전에 태어나신 그분 말이야!

 아, 호제법이란, 말 그대로 '서로 호(互)'자와 '덜 제(除)'자를 써서 '서로 나누어 없애는 방법'이라고 생각하면 돼. 아직 무슨 말인지 모르겠지?

 

 말로 백 번 설명하는 것보다 아래의 동영상을 보는 것이 훨씬 더 이해가 잘 될 텐데.. 동영상을 보기 전에 '%'라는 기호에 대해 알고 보아야 돼. '%'는 보통 '퍼센트'라고 해서 '백분율'로 많이 알고 있지? 하지만 컴퓨터 프로그래밍에서는 산술연산자로 쓰이는 경우가 많아. 산술연산자로 쓰일 땐 '나머지'를 구한다고 생각하면 돼.

 

 나머지를 구한다는 뜻을 기호로 나타내면,

 

 a%b

 

 이렇게 나타낼 수 있어. 이 뜻은 a를 b로 나눈 나머지를 구하겠다는 뜻이야.

 만약 10을 4로 나눈 나머지를 구하겠다고 하면,

 

 10%4 = 2

 

 이렇게 나타내면 되는 거지. 10을 4로 나누면 나머지는 2가 되겠지? 몫은 8일 테고 말이야.

 이 나머지 연산자(%)에는 몫은 필요 없어. 나머지만 알면 될 때 유용하게 사용할 수 있으니까 꼭 알아 둬!

 

 아무튼.. 나머지 연산자에 대해 알았다면 아래의 동영상을 보고 유클리드 호제법의 원리를 파악할 수 있을 거야.

 12와 15의 최대공약수를 구하는 방법을 유클리드 호제법을 사용해서 구해볼게.

 

(자몽이 목소리 출연)

 

 12의 약수는 1, 2, 3, 4, 6, 12 이고

 15의 약수는 1, 3, 5, 15 이잖아.

 여기서 12와 15의 공약수는 1, 3 이 되는데 공약수 중에 제일 큰 수가 3이니 3이 12와 15의 최대공약수가 되는 거지! 어때? 유클리드 호제법으로 구한 최대공약수와 같지? 아, 그리고 '최대공약수 最大公約數'는 'GCD'라고 줄여서 표기하기도 하는데, GCD는 Greatest Common Divisor의 앞 글자를 딴 약자야!

 

 이제 이 유클리드 호제법으로 두 수의 최대공약수를 구하는 코드를 만들어야 돼. 나는 파이썬 3로 코드를 만들었지만 여러분들은 다른 언어로 만들어도 돼~

 

def GCDofTwoNumbers(a, b):
    while b != 0:
        temp = a
        a = b
        b = a%b
    return a

 그럼 세 개 이상의 수는 최대공약수를 어떻게 구할 수 있을까? 간단해!

 

 먼저 아무 두 수 나 골라 잡고 두 수의 최대공약수를 구한 다음에, 구해진 최대공약수와 나머지 다른 숫자 하나를 묶어 잡고 묶어 잡은 숫자들의 최대공약수를 구하면 그게 바로! 세 수의 최대공약수가 되는거야.

 

 예를 들어서, 9, 12, 15이라는 숫자들이 있다고 치면,

 먼저 아무 숫자나 두 개 골라 잡아. 나는 9랑 12를 골라 잡아볼게. 9와 12의 최대공약수는 3이지? 그럼 이제 3과 나머지 다른 하나의 숫자로 남아 있는 15의 최대공약수를 구해야 돼. 3과 15의 최대공약수는 3이기 때문에 결국 9, 12 그리고 15의 최대 공약수 또한 3이 되는 거지!

 

 이제 이 방법을 파이썬 코드로 만들어볼까?

 리스트 arr에 공백 문자로 구분해서 숫자들을 입력받을 거야.

 

 그리고 위에서 만든 최대공약수를 구하는 함수를 사용할 건데, 리스트 arr에 입력된 숫자들에서 차례대로 최대공약수를 구하려고 해. 그런데 맨 첫 번째 항(초항)은 같이 묶어서 최대공약수를 구할 숫자가 없기 때문에 초항을 리스트 arr에서 가장 첫 번째(0번 방)에 있는 놈으로 할 거야.

 무슨 말이냐면, 어느 숫자든 똑같은 숫자 두 개의 최대공약수를 구하려고 하면 본인 자신이 나온다는 것을 이용한다는 말이야. 3과 3의 최대공약수는 3이 되겠지? 5나 7도 마찬가지야.

 

 이 알고리즘은 두 숫자의 최대공약수를 구해나가면서 여러 숫자의 최대공약수를 구하는 알고리즘인데, 초항과 묶어줄 놈이 없기 때문에 초항을 일부러 만들어 준거지!

 꼭 이렇게 하지 않아도 되지만, 고등 수학에서 초항에 대한 개념을 배우기 때문에 수열 공부했던 친구들은 초항의 개념을 바로 적용하라고 이렇게 짰어~ 그럼 이제 코드를 볼까?

 

GCDarr = arr[0]
for i in range(len(arr)):
    GCDarr = GCDofTwoNumbers(GCDarr, arr[i])
    print("GCDarr = ", GCDarr)
 
return GCDarr

 GCDarr이 가상의 초항이 되는 거야. 두 숫자를 묶어서 최대공약수를 구해야 하는데 리스트 arr의 첫 번째 항목(0번 방)은 묶을 대상이 없으니까!

 

 마지막으로 파이썬에서 동작할 전체 코드를 통해서 최대공약수를 구해보자!

 

arr = list(map(int, input().rstrip().split())) #공백문자로 구분하여 리스트 입력받기
 
def GCDofTwoNumbers(a, b): #GCDofTwoNumbers라는 이름의 함수와 매개변수 a, b 정의하기
    while b != 0 : #b가 0이 아닌 동안 반복
        a, b = b, a%b #a에 b를, b에 a와 b를 나눈 나머지를 교환하여 저장(스왑)
    return a #반환되는 a가 두 수의 최대공약수
 
GCDarr = arr[0] #arr 리스트의 첫 번째 항목(0번 방)을 GCDarr에 저장
for i in range(len(arr)): # i가 0부터 리스트 arr의 길이만큼 반복
    GCDarr = GCDofTwoNumbers(GCDarr, arr[i]) # GCDarr에 GCDarr과 arr[i]의 최대공약수를 저장
    print("GCDarr = ", GCDarr) #GCDarr의 값이 어떻게 달라지는지 보기 위한 출력
 
return GCDarr #반환되는 GCDarr이 리스트 arr의 최대공약수!

 나중에 에디터 가서도 쉽게 이해하라고 주석을 붙였어. 에디터 가서는 지워도 돼!

 

 지금으로부터 약 2300년 전 유클리드 아저씨가 만든 알고리즘이 아직까지도 잘 사용되고 있다니.. 역사의 한 현장에 있는 느낌이네! 이 유클리드 호제법이 인류가 만들어 낸 최초의 알고리즘이라니 믿겨? 참 재밌다니까~

 

 다음 글에서는 최대공약수를 이용해 최소공배수를 구해볼 거야!