[정글 TIL] 유클리드 호제법 , 재귀 알고리즘

오늘은 랜덤런치 날이라 다른 조원들과 함께 점심 식사를 했는데, 대부분 재귀함수에서 벗어나지 못하고 있었다. 나도 마찬가지라 (^.^) 재귀함수 문제 풀다가 도저히 공부없이는 해결을 못 할 것 같아서 교재를 펴서 재귀 알고리즘을 공부하기 시작했다. 재귀 알고리즘의 예제로 '유클리드 호제법'이 나왔는데 알고리즘은 고사하고 그냥 유클리드 호제법 자체가 이해가 안 가서 유클리드 호제법부터 공부했다. 어차피 이번주차 공부해야 할 내용중에 정수론도 있어서 겸사겸사 함께 공부! 

 

유클리드 호제법은 youtube에서 쑤튜브 채널 영상을 참고해서 이해했다. 

유클리드 호제법

유클리드 호제법은 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다는 것이다. 

즉, A = qB + r 이라면 (q는 몫, r은 나머지) gcd(A,B) = gcd(B,r) (단, A>B)이라는 것이다 (gcd()는 최대공약수를 나타내는 표기)

유클리드 호제법을 이용하면 직접 최대공약수를 구하기 어려운 큰 수들의 최대공약수도 빠르게 구할 수 있다!

e.g. gcd(384928104, 29348203) 는 gcd(384928104,29348203) 와 같고, 이는 gcd(29348203,3401465)와 같고, 이는gcd(3401465,2136483)와 같고, ... , 결국 gcd(2,1)와 같다는 것을 알 수 있다.

 ➡️ 2와 1의 최대공약수는 1이므로  gcd(384928104, 29348203)는 1이다. 

 

결국  A와 B의 최대공약수를 구하기 위한 방법은 아래와 같다. 

1. gcd(A, B)를 구하기 위해, gcd(B, B%A)를 구한다. (B%A는 B를 A로 나눈 나머지) 

2. gcd(B, B%A)를 구하기 위해, gcd(B%A, B%(B%A))를 구한다.

3. gcd(B%A, B%(B%A))를 구하기 위해, gcd(B%(B%A), B%(B%(B%A)))를 구한다. 

4. 이렇게 계속 구해나가다가, gcd(m,n)의 n이 0이 될 때의 m이 바로 최대공약수 이다. 

 

문자로 하니까 이해가 어렵다. 숫자로 같은 과정을 해보도록 하자. 24와 18의 최대공약수를 구해보자.

1. gcd(24,18)을 구하기 위해, gcd(18,6)을 구한다. 

2. gcd(18,6)을 구하기 위해, gcd(6,0)을 구한다. 

3. gcd(6,0)에서 두번째 인수가 0이므로 최대공약수는 6이다. 

 

이를 코드로 구현하기 위해서는 재귀함수를 사용할 수 있다. 

 

재귀 (recursion)  | 재귀 함수

재귀란 어떠한 이벤트에 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 것을 의미하고, 재귀함수란 자기 자신을 호출하는 함수이다(정확히는 '자기 자신과 동일한' 함수를 호출한다)

 

가장 많이 쓰이는 예제가 바로 factorial을 구하는 예제 인 것 같은데, 재귀함수를 쓰지 않고 factorial을 구할 경우 반복문을 돌려야 한다. 

# 반목문으로 factorial 구하기 [5! 구하기]

n = 5 # 5의 팩토리얼을 구한다.
total =1 
for i in range(1,n+1): # i값은 1,2,3, ... ,n 까지 반복된다
    total *= i  # 반복문을 돌 때마다 i값을 곱한다. 

print(total)

아래는 재귀함수로 5!를 구하는 방법이다.

# 재귀함수 정의
def factorial(n) :
    if n==1 :
        return 1
    else:
        return n * factorial(n-1)

# 재귀함수를 사용하여 5!구하기
print(factorial(5))

위 코드에서 factorial(5)를 실행하면 아래와 같은 순서로 코드가 진행된다.

1. factorial()의 매개변수인 5는 1이 아니므로 5*factorial(4) 를 리턴해야 하므로, factorial(4)를 구하기 위해 자기 자신과 동일한 함수인 factorial()을 호출한다 (재귀호출) 

2. factorial(4)의 매개변수인 4는 1이 아니므로 4*factorial(3) 를 리턴해야 하므로, factorial(3)를 구하기 위해 자기 자신과 동일한 함수인 factorial()을 호출한다 (재귀호출) 

3. factorial(3)의 매개변수인 3는 1이 아니므로 3*factorial(2) 를 리턴해야 하므로, factorial(2)를 구하기 위해 자기 자신과 동일한 함수인 factorial()을 호출한다 (재귀호출) 

4. factorial(2)의 매개변수인 2는 1이 아니므로 2*factorial(1) 를 리턴해야 하므로, factorial(1)를 구하기 위해 자기 자신과 동일한 함수인 factorial()을 호출한다 (재귀호출) 

5. factorial(1)의 매개변수는 1이므로 1을 리턴한다. ➡️ fatorial(1) = 1

6. 리턴값 1 을 전달받은 factorial(2)는 2*1 을 리턴한다.

7. 리턴값 2*1를 전달받은 factorial(3)는 3*2*1 을 리턴한다. 

8. 리턴값 3*2*1를 전달받은 factorial(4)는 4*3*2*1 을 리턴한다. 

9. 리턴값 4*3*2*1를 전달받은 factorial(5)는 5*4*3*2*1 을 리턴한다. 

 

자기 자신을 호출하는 재귀 함수를 통해 최대공약수를 구하는 알고리즘을 짜보면 아래와 같다. 

# 입력값으로 공백으로 구분된 숫자 두개를 받는 경우 (e.g. '24 18')
num_one,num_two = map(int,input().split())

# 함수 정의
def get_gcd(a,b):
    if b==0:
        return a
    else :
    	return get_gcd(b, a%b)

# 함수 실행 
get_gcd(num_one,num_two)

입력값이 '24 18'인 경우 코드의 실행과정은 아래와 같다. 

1. get_gcd(24,18)의 두번째 매개변수는 0이 아니므로, get_gcd(18, 6)를 리턴해야 하므로 자기 자신과 동일한 함수인 get_gcd()을 호출한다 (재귀호출) 

2. get_gcd(18,6)의 두번째 매개변수는 0이 아니므로, get_gcd(3, 0)를 리턴해야 하므로 자기 자신과 동일한 함수인 get_gcd()을 호출한다 (재귀호출) 

3. get_gcd(3, 0)의 두번째 매개변수는 0이므로 3을 리턴한다. 

4. 리턴값 3을 받은 get_gcd(18,6)는 그대로 3을 리턴한다. 

5. 리턴값 3을 받은 get_gcd(24,18)는 그대로 3을 리턴한다. 

 

---

사바타 보요, 『Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편』, 강민, 이지스퍼블리싱, 2020

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - YES24

 

정수론 2 강: 유클리드 호제법 [쑤튜브] link: https://www.youtube.com/watch?v=Obs-HC5j5bI