모두의 알고리즘 문제 05. 최대공약수 구하기

def gcd(a,b):  # Greatest Common Divisor, GCD, 최대공약수
    i = min(a,b)  # a, b 중 최솟값 i를 구한다. i가 최대공약수인지 검사한다.
    while True:  # 반복문의 실행조건이 True라서 중간에 강제로 중지시키지 않는 한 계속 돌아간다.
        if a%i==0 and b%i==0:  # i가 최대공약수라면 함수를 끝내버리는 것으로 반복문도 끝내버림.
            return i
        i = i-1  # i가 최대공약수가 아니면 1 줄이고 다시 돌린다.

print(gcd(1, 5)) #결과 1
print(gcd(3, 6)) #결과 3
print(gcd(60, 24)) #결과 12
print(gcd(81,27)) #결과 27
print(gcd(232, 112)) #결과 8


def re_gcd(a, b):
    if b==0:
        return a
    return re_gcd(b, a%b)

print(gcd(1, 5)) #결과 1
print(gcd(3, 6)) #결과 3
print(gcd(60, 24)) #결과 12
print(gcd(81,27)) #결과 27
print(gcd(232, 112)) #결과 8

첫 번째 최대공약수 구하기 알고리즘의 구조는 다음과 같다.

 

1. 최대공약수를 구하고자 하는 두 수 a, b 중 최솟값을 i로 저장한다.

2. i가 최대공약수인지 검사하기 위해 a와 b에 각각 나눠보고 나머지가 0인지 확인한다.

3. 나머지가 0이라면 i는 a와 b의 공약수이고 i==a이므로 최대공약수가 된다.

4. 나머지가 0이 아니라면 i를 1 줄이고 다시 검사한다.

 

 

두 번째 알고리즘은 또 재귀호출이다. 배워야하는 건 아는데 그만 보고싶다. 볼 때마다 자신감이 줄어든다.

 

두 번째 알고리즘은 유클리드 알고리즘을 응용했다.

 

유클리드가 발견한 최대공약수의 성질은 다음과 같다.

 

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

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

 

2번을 종료조건으로 재귀호출을 만들면 위와 같은 알고리즘이 된다. 이해를 위해 재귀호출 과정을 작성해보자.

 

호출 (60, 24)

-> 호출 (24, 60%24)

-> (24, 12) 

-> 호출 (12, 24%12)

-> (12, 0)

-> 어떤 수와 0의 최대공약수는 자기자신이므로 최대공약수는 12가 된다. 최대공약수를 반환.