[알고리즘을 위한 수학이론] 유클리드 호제법을 PS에 적용하기 -1 (Ft. C++)

 

유클리드 호제법 

학교에서 수학을 배울 때 정수 단원에서 잠깐 소개되었었던 그 이론을 다시 알아보고, 백준 문제와 함께 천천히 익혀보자.

---

두 개의 양수 a와 b의 최대공약수를 구하려면 "a와 b를 소인수분해"하면 된다. 

이 때 손으로 하나하나 인수분해하며 푸는 방법도 있지만, 사람이 계산할 수 없을 만큼 매우 큰 두 수의 최대 공약수를 구해야한다면 컴퓨터를 이용해야한다. 이를 위해 PS에선 "유클리드 호제법"을 사용한다.

 

유클리드 호제법에 대한 이론적인 설명은 다음과 같다. (출처: 수학독본, 한길사)

두 양수 a, b가 있고 a>=b일때, a를 b로 나눈 몫을 q, 나머지를 r이라고 하자.

a = b*q+r 
0<= r < b

정리하면 위와 같다. 이 때, 만약 r == 0이라면, 즉 a가 b로 나누어 떨어진다면 b가 a와 b의 약수이자 최대공약수이다.

또, 만약 r>0이라면 위 식에서  r = a - b*q 이고, a와 b의 임의의 공약수 e가 있다고 할 때 우변의 a-b*q는 e로 나누어 떨어진다. 즉,  r = e*x (단, e는 a와 b의 공약수)라 할 수 있으며 이에따라 r은 e로 나누어 떨어진다. e는 b와 r의 공약수가 된다. 여기까지의 가정을 정리하면 아래와 같다.

 

1. r은 a를 b로 나눈 나머지이다.

2. a와 b는 임의의 공약수 e를 가진다

3. r은 e로 나누어떨어지므로 e는 b와 r의 공약수이다.

 

더 나아가 e'를 b와 r의 임의의 공약수라고 가정해보자. 이렇게 하면, e'가 a를 나누어떨어지게 한다. (여러 가정은 생략하고 a = b*q+r이라는 식에서 a = e'(n+m)이 되기 때문에.. )

결국 e'는 a, b, r의 공약수이다. 이것으로 a와 b의 공약수는 b와 r의 공약수이고, 역으로 b와 r의 공약수는 다시, a와 b의 공약수인 것이다. 

1. r은 a를 b로 나눈 나머지이다.
2. a와 b는 임의의 공약수 e를 가진다
3. r은 e로 나누어떨어지므로 e는 b와 r의 공약수이다.
4. e'는 a, b, r의 공약수이다.
5. (a, b의 최대공약수) = (b, r의 최대공약수)

이 다음 과정으로 넘어가서,

b를 r로 나눈 나머지를 r1이라하면 앞선 과정과 마찬가지로 (a, b의 최대공약수) = (b, r의 최대공약수) = (r, r1의 최대공약수)가 된다. 이 방법을 나머지가 없을 때까지 반복하면 유한번의 나눗셈 과정을 통해 반드시 a,b의 최대공약수를 구할 수 있다. 

 

수학독본의 예시를 보자. 247과 962의 최대공약수를 유클리드 호제법에 의해 구해본다면,

962 / 247 = 247 * 3 + 221
247 / 221 = 221 * 1 + 26
221 / 26 = 26 * 8 + 13
26 / 13 = 13 * 2 + 0  //나누어 떨어짐!

따라서, 두 수 247과 962의 최대공약수는 13이다.

여기까지가 유클리드의 호제법에 대한 이론이었고, 이어서 알고리즘에 활용해보자.

 

참고자료 

수학독본

티스토리

https://infinitt.tistory.com/232