알고리즘[Algorithm] | 최대공약수를 계산하기 위한 유클리드 호제법

유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘이다.

호제법은 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘을 나타낸다고 하는데,

 

2개의 자연수 A, B(A > B)에 대해 A를 B로 나눈 나머지를 R이라고 하면 A, B의 최대공약수는 B, R의 최대공약수와 같다.

따라서 B를 R로 나눈 나머지 C를 구하고, 다시 R을 C로 나눈 나머지를 구하는 과정을 반복해서

나머지가 0이 되었을 때 나누는 수가 A, B의 최대공약수가 된다.

 

위키백과에서 위 설명을 읽었을 때 이해가 완벽하게 되지 않았고.. 어렵다는 생각이 들었는데 예시를 보니 생각보다 간단했다!

위키백과의 예시를 직접 한 단계씩 직접 작성하고 출력해 보면서 이해를 했다.

 

243, 135의 최대공약수를 찾는다고 할 때 구하는 순서는 다음과 같다.

 

1. 둘 중 큰 수를 a, 작은 수를 b라고 할 때 a를 b로 나눈 나머지 r을 구한다.
2. b를 r로 나누었을 때 나누어 떨어지지 않는다면 이 과정을 반복하고, 나누어 떨어진다면 b가 최대공약수가 되어 b를 반환한다.

이를 코드로 작성한다면 아래 소스코드와 같다.

def gcd(a,b):
  r = a % b
  if r == 0:
    return b
  else:
    return gcd(b, r)
 
print(gcd(243, 135)) # 27