[알고리즘] 최소공배수와 최대공약수 C++

0. 목차

• 최대공약수(Greatest Common Divisior) 의 개념
• 최대공약수 알고리즘 1 (시간복잡도 O( min(A ,B) ) )
• 최대공약수 알고리즘 유클리드 호제법 (시간복잡도 O(logN))
• 최소공배수(Lease Common Multiple)의 개념
• 최소공배수 알고리즘 (시간복잡도 O(logN))

---

1. 최대공약수(Greatest Common Divisior)의 개념

최대 공약수의 개념을 설명하기 위해선, 먼저 공약수의 개념을 짚고가자.

공약수란? 2개이상의 N개의 수가 있을때, N개의 숫자에 모두 나누어떨어지는 공통되는 약수를 의미한다.

 

예를들어 4, 10, 16 세개의 공약수를 살펴보자

4의 약수는 1, 2, 4

10의 약수는 1, 2, 5, 10

16의 약수는 1, 2, 4, 8, 16 이 된다.

여기서 공통되는 약수는 1, 2 두개가 된다. 이 두개가 공약수가 된다.

 

최대공약수는 말그대로 공약수중에서 최대인 공약수를 의미한다. 그럼 위의 예시에서 최대 공약수는 2가 된다.

---

2. 최대 공약수 알고리즘 1 (시간복잡도 O( min(A ,B) ) )

두개의 수 A와 B ( 단 A >= B )가 있다. A와 B의 최대공약수를 구하는 방법에는 뭐가있을까?

 

정말 단순한 방법으론 1~B까지 하나하나 A와 B를 나누어가며, 두 수 모두 나누어떨어지는 수 중 최대인 수를 구하면된다.

 

함수이름은 최대공약수의 약자인 GCD라고 하겠다. 이는 1~더 작은수 까지 하나하나 나누며, 두 수가 나누어떨어지면 최대공약수를 갱신해 나가는 방법이다.

int GCD1(int A, int B) {
	int GCD = 0;

	//A>=B로 만들어주기 위해
	if (A < B) {
		int temp = A;
		A = B;
		B = temp;
	}

	for (int i = 1; i <= B; i++) {
		//두 수가 모두 나누어떨어지면 공약수이므로 갱신
		if (A%i == 0 && B%i == 0) {
			GCD = i;
		}
	}
	return GCD;
}

---

반응형

3. 최대공약수 알고리즘 유클리드 호제법 (시간복잡도 O(logN))

위에서 설명했던 O(N)시간으로 최대공약수를 구하는 방법보다 빠른 알고리즘이다.

유클리드 호제법이라는 알고리즘을 사용할것인데, 여기서 사용할 원리는 다음과 같다.

 

증명은 다음과 같다.

먼저 A와 B의 최대 공약수를 G라고 하자. 그러면 다음과 같은 식이 성립한다.

a와 b의 값이 서로소인 이유는, 위에서 조건을 제시할때 A와 B의 최대 공약수가 G라고 했으므로, a와 b가 서로소가 아니라면, G가 최대공약수라는 조건이 망가지므로 서로소가 되어야만 한다. 

예를들어 G=10 이고, a와 b가 서로소가 아닌수일때 (a=4, b=6), A=40이 되고, B=60이 된다. 이렇게 되면, 40과 60의 최대공약수는 계산해보면 20이 되는데, 위의 조건인 최대공약수가 10이라는 조건과 일치하지 않게된다.

 

2번식에 1번을 대입하면 다음과 같다.

 

위의 식을 정리를 해보면 아래처럼 정리가 된다.

 

이때, B=b*G 이고, r = (a-bq)*G가 되는데, 우리가 처음 사용하려했던원리인 gcd(A,B) = gcd(B,r) 를 만족하기 위해선, b와 (a-bq)가 서로소라는 것을 증명해야한다.

 

귀류법을 이용하여 증명을 해볼것이다.

귀류법은 명제가 참이다 라는것을 증명하기 위해, 명제의 결론을 부정했을때 모순이 생기는것을 보여주며 간접적으로 명제가 참임을 증명해주는 방법이다.

 

먼저 결론을 부정해보자.

위의 b와 (a-bq)가 서로소가 아니라고 해보자. 이때 a와 b는 서로소라는 조건은 들고간다.

그렇다면 b와 (a-bq)사이에 k라는 공약수가 생길것이고, 다음과 같은 식이 성립한다.

2번식에 있는 b에 1번식을 대입하여 정리를 하면 다음과 같다

 

자 여기서 모순이 발생한다. 맨 처음 a와 b는 서로소라 했지만, 정리를 하고난 뒤, b=m1*k , a= (m1*q+m2)*k로 k라는 공약수가 생겨 서로소가 아니게 되어버렸다.

이렇게 모순이 발생하기 때문에 결론을 부정한것은 거짓이 된다는 명제가 되며, 자연스레 b와 (a-bq)가 서로소라는 명제가 참인것이 간접적으로 증명이 되었다. b와 (a-bq)가 서로소임이 증명되었기 떄문에 우리는 

gcd(A,B) = gcd(B,r) 의 원리를 사용할 수 있게 된것이다.

 

위의 유클리드 호제법을 코드로 옮기면 다음과 같다.

int Euclidean(int A, int B) {
	//베이스 케이스
    //a%b==0일경우, 최대공약수는 b가 된다.
	//a%b == 0 일경우, 다음 함수를 호출하면 A=b , B=0이 되므로, 최대공약수인 A(b)를 리턴
	if (B == 0) {
		return A;
	}
	else {
		return Euclidean(B, A%B);
	}
}

---

4. 최소공배수(Lease Common Multiple)의 개념

최소공배수도 최대공약수와 같은 개념이다.

먼저 공배수는 2개이상의 수중, 공통되는 배수를 뜻한다.

예를들어 4와 6의 공배수를 구해보자.

4의 배수는 4, 8, 12, 16, 20, 24, ......

6의 배수는 6, 12, 18, 24, .........

 

이 두 배수의 공통된 수는 12, 24, .... 가 되는 것이다.

최소 공배수는 이 공배수중 가장 작은수인 12를 의미한다.

---

5. 최소공배수 알고리즘 (시간복잡도 O(logN))

최소 공배수를 어떻게 구할까? 우리는 소인수를 이용할것이다.

예를들어보자. 30과 36의 최소 공배수를 구해보자.

30을 소인수분해를 해보면, 2*3*5 가 되고,

36을 소인수분해를 해보면, 2*2*3*3이 된다.

벤다이어그램을 그려보면 아래와 같다.

 

두수의 공배수는 위 그림에서 합집합(모든 소인수를 곱해준 값) 의 정수배를 의미한다. 가운데 교집합은 최대공약수의 소인수를 나타낸다.

따라서 최소공배수를 구해주기 위해선, 위에 그려진것처럼 합집합(모든 소인수를 곱해준 값)을 구해주면 된다. 코드로 구현을 해보면 아래와 같다.

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

여기서 GCD를 왜 나누어주나면, 집합을 배울때 아래와 같은 공식을 배웠을 것이다.

두개를 더해준 뒤, 중복되는 값(교집합)을 빼주는것이다. 하지만 우리는 곱해주었기 때문에, 교집합을 나누어주는것이다.