[Python] '최대공약수 구하기' 알고리즘

본문은 <모두의 알고리즘 with 파이썬>(길벗, 2017)을 학습하고 개인 학습용으로 정리한 내용입니다.

 

안녕하세요, 오늘은 Python으로 '최대공약수 구하기' 알고리즘 구현법에 대해 포스팅합니다.

2가지 방법을 소개하겠습니다.

 

1. 순수히 반복문, 조건문 활용

2. 재귀함수 이용 (유클리드 알고리즘)

---

 

#1. 순수한 반복문, 조건문 활용

최대공약수 알고리즘에 대해 생각해보면 다음과 같습니다.

 

1. 두 수 중 더 작은 값을 i에 저장한다.

2. i가 두 수의 공통된 약수인지 확인한다.

3. 공통된 약수이면 이 값을 결과값으로 돌려주고 종료한다.

4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복한다.

* (1은 모든 정수의 약수이므로 i가 1이 되면 1을 결괏값으로 돌려주고 종료한다.)

 

def gcd(a, b):
    i = min(a, b) # 두 수 중에서 최솟값을 구하는 파이썬 함수
    while True:
        if (a % i == 0) and (b % i == 0):
            return i
        i = i - 1

print(gcd(5, 1)) # 1
print(gcd(3, 6)) # 3
print(gcd(60, 24)) # 12

---

#2. 재귀함수 이용 (유클리드 알고리즘)

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다.

- a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a % b)

- 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n

 

이 문제는 a와 b의 최대공약수를 구하기 위해서 (a, b)보다 좀 더 작은 숫자인 (b, a % b)의 최대공약수를 구하는 과정을 이용하는 전형적인 재귀 호출 문제이다. (좀 더 작은 값으로 자기 자신을 호출합니다.)

 

재귀 호출이 무한히 반복되지 않도록 하는 데 필요한 종료 조건은 무엇일까요? 바로 '어떤 수와 0의 최대공약수는 자기 자신'이라는 성질이다. 이 성질이 종료 조건을 만들어 낸다. 즉, b가 0이면 재귀 호출을 멈추고 결과를 돌려 준다.

유클리드 알고리즘을 이용해 최대공약수를 구하는 프로그램을 만들면 다음과 같다.

 

def gcd(a, b):
    if b == 0: # 종료 조건
        return a
    return gcd(b, a % b)

print(gcd(1, 5)) # 1    
print(gcd(3, 6)) # 3   
print(gcd(69, 24)) # 3
print(gcd(81, 27)) # 27

---

오늘은 여기까지입니다. 다음 번에 또 다른 알고리즘으로 찾아뵙겠습니다.