최대공약수와 최소공배수 - 유클리드 호제법

 

 

 

3과 8의 최대공약수와 최소공배수는 얼마인가?

1과 24이다.

 

2와 4의 최대공약수와 최소공배수는 얼마인가?

2와 4이다.

 

12와 28의 최대공약수와 최소공배수는 얼마인가?

4와 96이다.

 

어떻게 구하는지 설명하라고 하면 매끄럽게 설명하기는 힘든데 구하라고 하면 잘 구한다.

그냥 직관적으로 딱 나오는 경우도 있고, FM대로 하면 두 수의 약수를 싹다 구하고 공통된거 찾아서.... 이렇게 구하는 방법이 있긴 하다.

 

그런데 알고리즘 문제를 푸는데 최대공약수와 최소공배수 개념이 나왔다? 

컴퓨터에게 하나 하나 논리적으로 설명해야 한다...

 

어떻게 최대공약수와 최소공배수를 구하는지 알아보자.

 

최대공약수 (Greatest Common Divisor)

말 그대로 공통 + 가장 큰 약수라는 의미이다.

 

최대공약수를 구하기 위한 알고리즘 중 하나로 유클리드 호재법이 있다.

 

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

좀 풀어서 이해해 보자.

 

gcd(a,b) = gcd(b,r) 이구나.

이러면 재귀로 풀 수 있겠는데? 라는 생각이 들기도 한다.

 

일단 먼저 예시로 28과 12를 위의 말대로 해 보자.a = 28 b = 12 나머지인 r = 4그럼 b랑 r 을 다시 나눠주고...최대공약수가 4가 나온다.

 

오 진짜 되네 신기하다. 이정도만 알면 코드 짤 수 있지.하고 넘어가지 말고 왜 이렇게 되는지 생각해 보자.

 

증명 부분을 보면

 

 

그렇다고 한다. 한번 이해해 보자.

 

a,b는 정수이니까 a = bq+r 로 표현할 수 있다. (초등학교 때 배운 나머지 검산식을 생각하자)

여기서 q는 a를 b로 나눈 몫이고 r은 나머지이다.

 

또 a와b의 최대공약수를 k 라고 하면 a = a' * k  // b = b' * k 로 표현할 수 있다.

a = bq + r 에서 위의 식을 적용하면 a'k = b'kq + r 이고

r = a'k-b'kq 즉 r = k(a'-b'q) 이므로 r은 k의 배수이고, k는 a와b의 공약수임을 알 수 있다.

이제 a'-b'q 와 b' 이 서로소임을 증명하면 k가 gcd(a,b)임을 확실하게 알 수 있다.

증명하는 방법에는 여러 가지가 있는데, 위의 증명처럼 귀류법을 사용해서 증명하자.

 

이산수학의 개념이 많이 들어가있지만, 이해가 안 되진 않는다.

위를 통해 최대공약수를 구했으면, 최소공배수를 구하는 건 쉽다.

 

입력받은 두 수를 곱한 후 최대공약수로 나누면 최소공배수가 나온다.

 

코드를 통해 정리하자

 

	static int gcd(int a, int b) {
		 // a > b 임을 가정함
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

반복문으로 작성한 코드이다.

 

	static int gcd2(int a, int b) {
		int r = a % b;
		if (r == 0) {
			return b;
		} else {
			return gcd2(b, r);
		}
	}

 

재귀로 작성한 코드이다.