목차
최대공약수 (GCD; Greatest Common Divisor)
- 최대공약수가 뭔지는 생략해도 충분할듯.
- 한국어 위키피디아에는 ko:최대 공약수로 등록되어있지만, 띄어쓰기 없이 붙여 쓰는게 맞다고 한다.
최대공약수 알고리즘
- 최대 공약수를 구하는데 걸리는 최적의 시간복잡도는 O(log(max(n,m))) 이다
- O(log(max(n,m)))에 최대 공약수를 구하는 가장 일반적이고 잘 알려진 방법은 유클리드 알고리즘이다. 하지만, 시간복잡도는 같지만 실용적으로 좀 더 빠르게 돌아가는 Binary GCD 알고리즘이나 Lehmer's algorithm 등도 있다.
- 파이썬에서는 math.gcd 함수에 구현되어 있기 때문에, 굳이 직접 구현할 필요는 없다.
- 내부 구현은 Lehmer's algorithm 이라고 한다.
유클리드 알고리즘
- Euclidean algorithm (Euclid's algorithm 으로도 불린다)
- 유클리드 호제법이라고도 불린다.
- 두 양의 정수의 최대 공약수를 구하기 위해 사용되는 알고리즘. 중학교 수학 교과에도 포함되어 있고, 코딩 과목을 듣다보면 코드로 짜는 연습도 한번쯤은 해보게 된다.
- 기원전 300년경에 기록되어서, 인류 최초의 알고리즘으로도 알려져있다.
- 원래 알고리즘은 스텝마다 나눗셈을 하는게 아니라, 스텝마다 뺄셈을 하는 방식이었다고 한다.. 이건 좀 느린데..
- 로직도 심플하고 코드도 간단하게 작성 가능하다 (재귀함수로 구현하면 한줄에도 가능).
- 유클리드 알고리즘으로 GCD(n,m)을 구할때 필요한 나눗셈의 횟수는 O(log(max(n,m)))이다.
- PS에서는 나눗셈을 O(1)로 취급하니까 그냥 시간복잡도가 O(log(max(n,m)))이라고 생각하면 간단하다.
- 이것을 제대로 처음 증명한것이 Lamé's Theorem인데, 계산복잡도 이론의 시초라고 한다
Binary GCD algorithm
- Stein's algorithm 이라고도 불리긴 하지만, 실제로는 스타인이 1967년에 발표하기 훨씬전인 기원전 2세기에 중국에서 이미 알려져 있었다고 한다.
- 나눗셈을 쓰지 않고, 비트쉬프트연산과 뺄셈만으로 GCD를 구하도록 개선된 알고리즘
- 시간복잡도는 유클리드 알고리즘과 동일하게 O(log(max(n,m))이지만, 실질적으로는 더 빠르게 돌아간다고 한다.
Lehmer's GCD algorithm
- 큰수들 간의 GCD를 구할때 효율적이다
- cpython의 math.gcd는 이 알고리즘으로 구현되어 있다
- Pypy에서는 그냥 유클리드 알고리즘으로 구현되어있기 때문에, 큰수의 GCD를 구할 때에는 pypy가 훨씬 느리다는 이야기가 있다. (https://foss.heptapod.net/pypy/pypy/-/issues/3031)
최대공약수의 활용
- 최대공약수는 정수론에서 가장 기본이라서, 온갖 것을 구할때에 활용된다..
- 그런것 말고 단순히 최대공약수만을 활용하는 문제 유형을 적어보겠다.
격자점 위에서 선분이 지나는 점의 갯수
- 격자점들 위에서 (0,0) ⇒ (a,b)로 선분을 그었을때, 선분위에 있는 격자점의 개수는 gcd(a,b)+1 개이다.
모눈종이 위에서 (0,0) ⇒ (a,b)로 선분을 그었을 때, 선분이 지나는 정사각형의 개수는 a+b-gcd(a,b) 개 이다
베주 항등식
- 이름은 항등식인데, 내용은 정리에 가깝다. (Bézout's lemma 라고도 불린다고 한다)
- 내용은
- 두 정수 n, m 이 있을때, nx+my=gcd(n,m) 을 만족시키는 정수 x와 y가 반드시 존재한다
- 정수 x와 y에 대해서 nx+my=d 를 만족시키는 정수 d는 항상 gcd(n,m)의 배수이다.
- 여기서 바로 알수 있는 것들은
- nx+my=c 라는 부정방정식이 있을때, c가 gcd(n,m)의 배수가 아니라면 x,y의 정수해가 존재하지 않는다
- (x0, y0)가 nx+my=d 의 하나의 해일때, 일반해는 (x0 + k*m/gcd(n,m), y0 - k*n/gcd(n,m)) 이 된다
확장 유클리드 알고리즘 (Extended Euclid Algorithm)
- m과 n이 주어졌을때, nx+my=gcd(n,m) 을 만족시키는 정수 x0와 y0, 그리고 gcd(n,m)을 함께 구하는 알고리즘
- 이런 x,y가 존재한다는 것은 베주 항등식에서 알수 있다.
- 코드는 유클리드 알고리즘을 조금만 수정하면 된다. 시간복잡도도 동일하게 O(log(max(n,m)))
- 이제 nx+my=c 의 해를 다음 과정으로 구할 수 있다.
- 확장 유클리드 알고리즘을 통해서 gcd(n,m)과 nx+my=gcd(n,m)를 만족시키는 x0, y0 를 구한다
- c % gcd(n,m) != 0이면 해가 없다. 그렇지 않으면 x0*c/gcd(n,m), y0*c/gcd(n,m) 이 nx+my=c 의 해가 된다
- 일반해는 (x0*c+k*m)/gcd(n,m), (y0*c-k*n)/gcd(n,m) 이 된다
- 확장 유클리드 알고리즘이 사용되는 가장 흔한 경우는 모듈러 역원을 계산하는 것이다.
- a의 m에 대한 모듈러 역원 x는 a*x % m = 1 을 만족하는 x이다
- 이걸 다시 쓰면 ax-my = 1 이 된다. 즉, gcd(a,m)이 1보다 크면 역원이 없고, 서로소라면 a,m에 대해서 확장 유클리드 알고리즘을 돌리면 x값을 찾을수 있다.
- 파이썬에는 pow함수가 모듈러 역원을 계산해주기 때문에 모듈러 역원 계산을 위해서 확장 유클리드 알고리즘을 새로 코딩할 필요는 없다. 오히려 역으로 pow함수를 이용해서 확장 유클리드 알고리즘을 구현하는 것도 가능하다.
- nx+my=gcd(n,m)를 만족하는 정수 x0,y0을 찾는다고 하자.
- 먼저 math.gcd를 이용해서 gcd(n,m) = g 를 계산하자
- 양변을 g로 나눠서 (n/g)x + (m/g)y = 1 로 만들고 이항하면, (n/g)*x ≡ 1 mod (m/g) 가 되므로 x=pow(n/g, -1, m/g)로 계산할수 있다. y도 마찬가지로 y=pow(m/g, -1, n/g) 으로 계산하면 된다.
- gcd를 먼저 구하고 역원을 다시 구해야 하므로 속도상으로는 좀 비효율적일수 있지만, 계산 자체가 가벼워서 별로 차이는 안난다. 확장 유클리드 알고리즘을 반복해서 적용해야 하는 문제를 본적도 없어서 별 신경 안써도 될것 같다
- 그것보다는, 그냥 확장 유클리드 알고리즘 코드를 구현해도 워낙 심플하기 때문에 굳이 이렇게 회피해야 하는가 하는 생각은 든다.