#4-5-2 The Art of Computer Programming - 준수치적 알고리즘

이번절은 최대공약수(gcd)에 대한 내용이다.

알다시피 최대공약수는 u와 v가 정수이며 둘 다 0이 아닐 때, 두 수를 모두 나누어 떨어지게 하는 가장 큰 정수를 일컫는다.

이러한 정의들로 아래의 항등식이 성립한다.

gcd(0,0) = 0

gcd(u,v) = gcd(v, u)

gcd(u, v) = gcd(-u, v)

gcd(u,0) = |u|

 

최소공배수(lcm)는 u, v 모두 정수배인 가장 작은 양의 정수로 정의된다.

lcm(u,0) = lcm(0, u) = 0

 

이전 절에서 산술의 기본정리를 따르면 모든 양의 정수는 소수로 표현될 수 있다.

나는 기억이 없으나.. 그렇다고 하는데, 매우 신기하다. 그래서 gcd와 lcm은 다음과 같이 정리가 가능하다.

 

gcd(u, v) = 각 소수들 ^ min(u_p, v_p)

lcm(u, v) = 각 소수들 ^ max(u_p, v_p)

 

예를 들어,

u = 7000 = 2^3 * 5^3 * 7

v = 4400 = 2^4 * 5^2 * 11

 

gcd(u, v) = 2^min(3,4) * 5^min(3,2) * 7^min(1,0) * 11^min(0,1) = 2^3 * 5^2 = 200

gcd(u,v) = 2^min(3,4) * 5^min(3,2) * 7^min(1,0) * 11^min(0,1) = 2^4 * 5^3 * 7 * 11 = 154000

으로 구할 수 있다.

 

그러나 상기의 방법은 이론적으로 유용하지만 실제로는 사용이 어려운데,

그 이유는 인수분해를 통해 소수의 제곱 형태로 나타내야 하기 때문이다.

 

그래서 유클리드 알고리즘을 사용한다. 이 알고리즘은 문제풀이에서 꽤나 많이 등장하는 방법 중 하나다.

u, v 중 큰 수를 u로 놓고

u가 0이면 u를 답으로 출력하고 끝내고

아니면 r = u mod v를 계산 후, u <- v, v <- r로 놓고 다시 진행한다.

 

그 외의 이진 방법 및 여러 분석 내용들을 소개하는데 뒤로 갈수록 수식이 많아 이해하기가 난해하다. ㅠㅠ

 

그래도 다른 절들에 비해 배경지식이 있는 내용이라 그런지 꽤 잘 읽혔던 것 같다.