[Algorithm] 최대공약수(Gcd) : 유클리드 호제법 원리

#유클리드 호제법

유클리드 호제법이란 두 자연수 사이의 최대공약수(Gcd)를 구하는 알고리즘 중 하나이다.

두 자연수 a, b(a>b)에 대하여 a를 b로 나눈 나머지를 r이라고 하자.

그러면 Gcd(a, b) = Gcd(b, r)와 같고, r = 0이 될때까지 이 과정을 반복했을때 b의 값이 두 수의 최대공약수가 된다.

#예시

두 수 1248과 462의 최대공약수를 유클리드 호제법을 이용하여 구해보자.

a = 1248, b = 462라 하면 

• 1248 = 462 * 2 + 324

이때 Gcd(1248, 462) = Gcd(462, 324)이고, 다시 a= 462, b = 324라 하면

• 462 = 324 * 1 + 138

마찬가지로 Gcd(462, 324) = Gcd(324, 138)이다.

이 과정을 r = 0이 될 때까지 반복하면 다음과 같다.

• 324 = 138 * 2 + 48
• 138 = 48 * 2 + 42
• 48 = 42 * 1 + 6
• 42 = 6 * 7 + 0

따라서 Gcd(1248, 462) = Gcd(462, 324) = ... = Gcd(42, 6) = Gcd(6, 0) 이고, 

두 수의 최대공약수는 6이 된다.

---

#구현

1. 재귀함수

int gcd(int a, int b)
{
	if (a > b) {
		if (b == 0)
			return a;
		else
			return gcd(b, a % b);
	}
}

위 코드는 유클리드 호제법을 재귀함수로 구현한 코드이다.

자기자신을 계속해서 호출하다가, 나머지가 0이 될 때 a값을 반환하고 종료된다.

 

2. 반복문

int gcd(int a, int b)
{
	int temp;
	if (a > b) {
		while (b > 0) {
			temp = a;
			a = b;
			b = temp % a;
		}
		return a;
	}
}

위 코드는 유클리드 호제법을 반복문으로 구현한 코드이다.

재귀함수는 문제가 발생할 가능성이 다분하므로, 위 반복문과 같이 변경할 수 있다.

나머지가 0이 될때 while문을 빠져나와, a값을 반환하고 종료된다.

 

유클리드 호제법은 두 수의 최대공약수를 구할 때 유용하게 사용하는 알고리즘이니 잘 기억하도록 하자.