[Algorithm] Euclidean algorithm GCD 유클리드 호제법 최대공약수

Euclidean algorithm 은 유클리드 호제법이라고도 하며,

이 알고리즘으로 Greatest Common Divisor; GCD 최대공약수를 구할 수 있습니다.

(GCD 를 응용해 Least Common Multiple; LCM 최소공배수도 구할 수 있어용)

 

---

 

유클리드 호제법 (GCD 최대공약수)

두 양의 정수 a, b (a > b) 에 대하여, a = bq + r (0 <= r < b) 이라고 하면,
a, b 의  최대공약수는 b, r 의 최대공약수와 같다. 즉,
gcd(a, b) = gcd(b, r)
r = 0 이라면, a, b 의 최대공약수는 b 가 된다.

 

쉽게 말하자면, 큰 놈과 작은 놈의 최대공약수는,

큰놈 % 작은놈 = R 이라고 할 때, (큰놈을 작은놈으로 나눈 후 나머지를 R 이라고 할 때,)

R 과 작은놈의 최대공약수와 같습니다.

 

그렇기 때문에 이를 반복하면 최대공약수를 구할 수 있습니다.

GCD(a, b) == GCD(b, a % b) // 참

 

위 와 같은 조건을 반복하며 나머지가 0이 되는 순간, 그 때가 b 의 최대공약수인 셈입니다.

 

예시로, GCD(48, 18) 을 계산하는 과정을 정리해보도록 하겠습니다.

	a	b	a % b
1회	48	18	12
2회	18	12	6
3회	12	6	0

 

이렇게 GCD 함수가 3번 반복해서 수행하다가 a % b (나머지) 값이 0 인 시점에서 완료됩니다.

따라서, GCD(48, 18) = 6 입니다.

 

예시 코드

그냥 반복문 (brute force 로 그냥 반복문 돌려보는 거죵) 으로 했을 경우, 시간복잡도는 O(n) 입니다.

시간복잡도에 대한 성능은 아래링크를 확인해주시면 좋겠습니다.

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95#s-3.4

유클리드 호제법

 

아래는 그냥 반복문 (brute force) 로 유클리디언 호제법 최대공약수를 구현했을 때 입니다.

int gcd = 1;
for (int i = 2; i <= Math.Min(a, b); i++) {
	if (a % i == 0 && b % i == 0)
    	gcd = i;
}

 

보통 위 방법은 잘 사용하지 않습니다.

 

유클리드 호제법으로 할 경우 아래와 같습니다.

int GCD(int a, int b) {
	while (b != 0) {
    	int temp_R = a % b;
        a = b;
        b = temp_R;
    }
    return a;
}

 

02번 라인에서 b 가 0 일 때까지, 계속 반복합니다.

03번 라인에서 a % b 나머지를 temp_R 에 저장합니다.

07번 라인에서 b 가 저장된 a 를 리턴하므로,

저흰 맨 처음 a, b 의 최대공약수를 구할 수 있습니다.

 

재귀함수 (Recursive) 로 쓴다면 아래와 같겠습니다.

int GCD(int a, int b) {
	if (b == 0)
    	return a;
    return GCD(b, a % b);
}

 

위에 GCD(48, 18) 로 호출한다면,

GCD(48, 18) → GCD(18, 48 % 18) → GCD(18, 12) → GCD(12, 18 % 12) → GCD(12, 6)
→ GCD(6, 12 % 6)   → GCD(6, 0) → return 6

 

위 처럼 재귀적으로 호출되다 6 을 리턴하며 재귀함수가 종료되겠습니다.

※ StackOverFlowException (몇 천번 ~ 만번 재귀를 깊게하면 좀 거시기할 수도 있어용)

 

LCM 최소공배수

Least Common Multiple; LCM 최소공배수는 GCD 를 응용해서 구할 수 있습니다.

아래 LCM 과 GCD 의 관계식을 보겠습니다.

LCM(a, b) = (a * b) / GCD(a, b)

 

이렇게 GCD 만 구할 수 있다면 LCM 도 한줄로 구할 수 있습니다.

int GCD(int a, int b) {
	if (b == 0)
    	return a;
    return GCD(b, a % b);
}

int LCM(int a, int b) {
	return (a * b) / GCD(a, b);
}

 

위 처럼 GCD 만 알고 있다면 아주 간단합니다.

a * b 가 너무 커질 경우를 대비해 아래처럼 long 으로 사용하시는 것도 추천드립니다.

long LCM(int a, int b) {
	return (long)a * b / GCD(a, b);
}

 

---

 

별로 어렵지 않기 때문에, 알아두면 좋을 듯 싶습니다.

기약분수 같은 연산할 때도 쓸 수 있어요!

그럼 좋은 하루 되시길 바라용~ ૮₍ *•͈ ꇴ •͈* ₎ა