[Algorithm] 유클리드 알고리즘

1. 최대공약수(Greatest Commom Divisor, GCD)

공약수는 두 수 이상의 여러 수의 공통된 약수를 의미한다. 여기서 최대공약수는 두 수 이상의 여러 수 공약수 중 최대인 수를 가리킨다. 예제를 통해 살펴보자. 여기서 50과 90의 최대공약수를 구해보자

최대공약수

최대 공약수는 10임을 확인할 수 있다. 

2. 최소공배수(Lowest Common Multiple, LCM)

공배수는 두 수이상의 여러 수의 공통된 배수를 의미한다. 여기서 최소공배수는 두 수 이상의 여러 수 공배수중 최소인 수를 가리킨다. 예제를 또 하나 살펴보자. 여기서 10과 30의 최소공배수를 구해보자

최소공배수

 최소 공배수는 30이 됨을 확인할 수 있다. 최소 공배수는 (두 자연수의 곱 / 최대 공약수)로도 구할 수 있다. 

3. 유클리드 호제법(Euclidean Algorithm)

유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, 여기서 a > b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다 이 성질을 이용해 b를 r로 나눈 나머지 r'를 구하고 다시 반복하며 나머지를 구하는 과정을 이어나가다가 나머지가 0이되었을 때, 나누는 수가 a와 b의 최대 공약수이다.

1번의 예제를 통해 위의 방식처럼 최대공약수를 구해본다. 

 - 90은 50으로 나누어 떨어지지 않으므로, 나머지를 구함 -> 40

 - 50은 40으로 나누어 떨어지지 않으므로, 나머지를 구함 -> 10

 - 40은 10으로 나누어

떨어짐

따라서 최대공약수는 10임을 알 수 있다. 더 나아가 조금 큰 숫자로 진행해보자. 78696과 19332의 최대 공약수를 구해보자

    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

위의 식대로 진행하면 최대공약수는 36이 나옴을 알 수 있다. 이제 이 방법을 코드로 구현해본다. 간단하게 알고리즘을 정리하면 아래와 같다

 1. 입력으로 두 수 A, B(A > B) 주어짐

 2. B가 0이면, A를 출력 후 알고리즘 종료

 3. A가 B로 나누어 떨어지면, B를 출력하고 알고리즘 종료

 4. 그렇지 않으면 A를 B로 나눈 나머지를 새롭게 A에 대입한 후, A와 B를 바꾸고 3번으로 돌아감

이를 코드로 정리하면 재귀방식과 반복문방식 두가지가 존재한다. 

 - 재귀

int gcd(int A, int B) {
    if (B == 0) return A;
    else return gcd(B, A % B);
}

 - 반복문

int gcd(int A, int B)
{
    int R;
	while(B)
	{
		R = A % B;
		A = B;
		B = R;
	}
    return A;
}

---

참고 문서

http://www.tcpschool.com/codingmath/common

코딩교육 티씨피스쿨

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전