티스토리 뷰

Table of Contents


개요

유클리드 호제법

시간복잡도

최대공약수에 대해 알아둬야 할 것

문제




1. 개요


 두 수 n, m 의 최대공약수를 구할 때, 유클리드 호제법을 이용하면 시간복잡도 O(log(n+m))만에 구할 수 있습니다.




2. 유클리드 호제법


 gcd(n,m) = gcd(n-m,m), 그리고 더 나아가 gcd(n,m) = gcd(n%m,m) 임을 이용해 최대공약수를 빠르게 찾는 방법입니다. (n,m 은 자연수) (편의상 n, m 의 최대공약수 = gcd(n,m) 으로 표현하겠습니다.)



 gcd(n,m)을 gcd(n%m,m)으로 바꾸는 과정을 한 쪽이 0이 될 때 까지 진행하면 다음과 같이 구현할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
 
using namespace::std;
 
int get_gcd(int v1,int v2){
    if(v1>v2) swap(v1,v2);
    if(v1==0return v2;
    return get_gcd(v2%v1,v1);
}
cs




3. 시간복잡도


 일반성을 잃지 않고, n >= m 이라고 가정하겠습니다. ( n = max(n,m) )

 이 때, m >= n%m 임은 나머지 연산의 특성을 고려하면 자명합니다.

 그러므로 아래와 같이 get_gcd가 호출됩니다.


 get_gcd(n,m) -> get_gcd(n%m, m) -> get_gcd(m%(n%m), n%m)


 이 때, get_gcd(m%(n%m), n%m) 가 호출될 때까지 상수 번의 연산이 필요했음은 자명합니다. ............ 1


 m%(n%m), n%m 중 최댓값은 n%m 입니다. ................. 2


 n>=m 일 경우, n > 2*(n%m) 이 성립합니다. ....................3




1, 2를 종합하면 상수 번의 연산으로 두 수 중 최댓값이 n에서 n%m 으로 바뀌었고, 이는 3에 의해 최댓값이 절반 이하가 되었음을 의미합니다. 이를 통해 위 소스의 시간복잡도는 O( log ( max(n,m) ) ) 임을 증명할 수 있습니다. 상수 번의 연산으로 최대값이 절반 이하가 되었기 때문이지요. 또한 이를 간단한 표기로 바꾸면 O( log(n+m) ) 이 됩니다.




4. 최대공약수에 대해 알아둬야 할 것


(1) LCM (a, b) = a * b / gcd (a, b) 이다. (* LCM (a, b) = a와 b의 최소공배수)


(2) gcd (a, gcd (b, c)) = gcd(gcd(a, b), c) 가 성립한다.


이 특징으로 인해 '구간에 있는 모든 수들의 gcd' 가 필요할 때, Segment tree 나 Sparse table 을 활용해 볼 수 있습니다.




5. 문제


(0) [BOJ 2609] 최대공약수와 최소공배수


(1) [BOJ 1188] 음식 평론가


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.