05. 최대공약수 구하기

두 자연수 a와 b의 최대공약수를 구하는 알고리즘을 만들어보자. 

최대공약수 (Greatest Common Divisor, SCD) : 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미

① 두 수의 약수 중에서 ②공통된 것을 찾아 ③그 값 중 최댓값인 것을 찾아야 한다. 

<1> 최대공약수 알고리즘

---

GCD 성질을 떠올리며 다음 알고리즘을 생각해 보자.

1. 두 수 중 더 작은 값을 i에 저장
2. i가 두 수의 공통된 약수인지 확인
3. 공통된 약수이면 이 값을 결과값으로 돌려주고 종료
4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복(1은 모든 정수의 약수이므로 i가 1이  되면 1을 결과값으로 돌려주고 종료)

예제 : '4'와 '6'의 GCD를 찾아보자

1. i에 4를 저장
2. 4는 i로 나누어 떨어지지만, 6을 떨어지지 않음
3. i를 1만큼 감소시켜 3으로 만든다.
4. 4는 i로 나누어 떨어지지 않음
5. i를 1만큼 감소시켜 2로 만듬
6. 4도 i로 나누어떨어지고, 6도 i로 나누어떨어지므로 i값 2가 GCD이다.

최대공약수를 구하는 알고리즘

# 최대공약수 구하기
# 입력 : a, b
# 출력 : a와 b의 최대공약수

def gcd(a, b):
    i = min(a, b)    # 두 수 중에서 최솟값을 구하는 파이썬 내장 함수
    while True:
        if (a % i) == 0 and (b % i) == 0:
            return 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

 

실행결과

1
3
12
27

<2> 유클리드 알고리즘

---

위에서 본 코드는 최대공약수의 정의에 충실하면서 직관적인 알고리즘이다. 이번에는 유클리드가 발견한 GCD의 성질을 이용하는 다른 알고리즘을 살펴보자.

Euclid는 최대공약수에 다음과 같은 성질이 있다는 것을 발견했다.

• a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) == gcd(b, b % a) 이다.
• 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n 이다.\

예제 : 60과 24의 최대공약수를 구하는 것, 81과 27의 최대공약수를 구하는 것

gcd(60, 24) = gcd(24, 60 % 24) = gcd(24, 12) = gcd(12, 24 % 12) = gcd(12, 0) = 12

gcd(81, 27) = gcd(27, 81 % 27) = gcd(27, 0) = 27

몇 번만 계산해보면 GCD를 쉽게 얻을 수 있다. 그런데 풀이 과정을 유심히 살펴보면 어떤 두 수의 최대공약수를 구하기 위해 다시 다른 두 수의 최대공약수를 구하고 있는 것을 알 수 있다. 이것이 바로 "재귀 호출"로 이 문제를 풀 수 있다는 힌트다.

유클리드 방식을 이용해 최대공약수를 구하는 알고리즘

# 최대공약수 구하기 (유클리드 방법)
# 입력 : a, b
# 출력 : a와 b의 최대공약수


def gcd(a, b):
    if b == 0:              # 종료 조건
        return a
    return gcd(b, a % b)    # 좀 더 작은 값으로 자신 호출


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

실행 결과

1
3
12
27

 

재귀 호출의 이해를 돕는 방법

---

자기가 자기를 호출한다는 개념을 이해했더라도 막상 재귀 호출 프로그램을 보면 머릿속이 혼란스러울 때가 많다. 그럴 때는 다음과 같은 방법을 이용해보자.

• 종이에 직접 적어 호출 과정을 적어보자.
• 예제로 사용할 입력 값은 작은 것이 좋으므로, 일단 종료 조건에 해당하는 값을 입력으로 넣은 다음 차차 입력 값을 높이면서 재귀 호출 과정을 따라가보자.
• 함수의 입력 값을 화면에 출력하는 것도 도움이 된다.

def gcd(a, b):
    print("gcd: ", a, b)    #함수 호출을 입력(인자) 값과 함께 화면에 표시
    if b == 0:              # 종료 조건
        return a
    return gcd(b, a % b)    # 좀 더 작은 값으로 자신 호출


print(gcd(60, 24))

gcd:  60 24
gcd:  24 12
gcd:  12 0
12

입력인자가 순차적으로 어떻게 들어가게 되는지 확인하면 이해가 쉬워진다.

 

연습문제

---

0과 1부터 시작해서 바로 앞으 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 피보나치 수열이라고 한다. 즉, 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3이므로 피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

피보나치 수열이 파이썬의 리스트처럼 0부터 시작한다고 가정했을 때 n번째 피보나치 수를 구하는 알고리즘을 재귀 호출을 이용해서 구현해보자. (힌트 : 7번 값 = 5번 값 + 6번 값)

# n번째 피보나치 수열 찾기
# 입력 : n값(0부터 시작)
# 출력 : n번째 피보나치 수열 값

def fibo(n):
    if n <= 1:
        return n    # n = 0 -> 0 | n = 1 -> 1
    return fibo(n-1) + fibo(n-2)


print(fibo(3))

2