약수와 배수
약수/배수 판별
나머지의 특징을 이용하면 두 정수의 약수/배수 관계를 판별할 수 있습니다. 두 정수 a와 b에 대하여 몫과 나머지를 x, y 라고 할 때에 아래와 같은 식이 성립함을 알고있습니다.
a = xb + y
이 때 y(나머지)가 0이 되는 경우, a = xb가 되어 a는 b로 나누어 떨어지며 이 때 b는 a의 약수라 할 수 있습니다.
이처럼 '나머지가 0이다'와 'b는 a의 약수이다'는 서로 동치가 됨을 알 수 있습니다. 또한 'b가 a의 약수이다'는 'a가 b의 배수이다'와 동치입니다.
그러므로 우리는 % 연산자와 if문을 통하여 두 정수의 약/배수 관계를 쉽게 판별할 수 있습니다.
bool isMultiple(int mul,int div)
{//mul이 div의 배수이면 true, 아니면 false
return (mul % div) == 0;
}약수의 특징
어떤 수의 약수는, 나누어서 나머지가 0이 된다는 특징 외에도 재미있는 규칙성을 보입니다.
양의 정수 n, a, b에 대해 n=a*b (단, a <= b) 라고 해봅시다. 그러면 a와 b는 n의 약수가 됨을 알 수 있습니다.
a와 b의 값을 생각해봅시다. a의 최소값은 1이 되며, 이 떄 b는 n이 됩니다. 위의 식이 성립하기 위해서는 a가 점점 커질수록 b는 작아져야 하는 반비례 관계임을 알 수 있습니다.
위의 식 n=a*b에서 약수 a가 존재하면, 곱해서 n이 되는 짝 b가 항상 존재합니다. 즉, 모든 약수는 곱해서 n이 되는 쌍이 존재하며, (a, b) 꼴 쌍에서 a <= b라고 할 경우 a의 최대값은 sqrt(n)가 됩니다.
그 이유는 a <= b 가 성립하는 상태에서 a가 가장 커질 수 있는 경우는 a == b인 경우이고, 이는 n=a*a꼴이 됩니다.
이러한 특징은 이후에 소수 판별에서 중요한 특징으로 사용될 수 있습니다.
최대공약수와 최소공배수
앞에서 나머지가 가지는 특징와 약수/배수와의 관계에 대해서 설명했습니다. 이번 토픽에서는 조금 특수한 수들인 최대공약수와 최소공배수를 빠르게 계산할 수 있는 알고리즘을 설명할까 합니다. 먼저 최대공약수의 정의는 아래와 같습니다.
최대공약수(最大公約數)란, 0이 아닌 두 정수나 다항식의 공통되는 약수 중에서 가장 큰 수를 말한다. 두 정수 a와 b의 최대공약수를 기호로 gcd(a,b)로 표기한다. (위키피디아 발췌)
최소공배수는 최대공약수와는 반대로, 두 정수가 공통적으로 가지는 배수 중 가장 작은 값을 의미합니다. 최소공배수는 최대공약수와 밀접한 관계가 있는데, 정수 a, b의 최대공약수 G = gcd(a, b)에 대하여 아래의 식을 만족하는 정수 x와 y가 존재합니다.
a = Gx, b = Gy (단, x, y는 정수)
이 때 a b = GGxy 임을 알 수 있고, G는 두 수의 최대 공약수이며 x와 y는 서로소인 관계를 가집니다. 집합적으로 생각하면, a와 b의 합집합은 G, x, y이고 이 세 수를 곱한 Gxy가 최소공배수가 됨을 알 수 있습니다. 그러므로 두 수의 최소공배수 L = lcm(a, b)은 L= lcm(a, b)= a * b / gcd(a, b)이 성립합니다.
Brute Force 구현 - O(max(a,b))
가장 단순하고 직관적인 방법을 생각해봅시다.
두 정수 a와 b가 있다고 할 때에, a의 약수 이면서 b의 약수인 수 중 최대값이 바로 최대공약수가 됩니다. 그렇다면 우리는 [1, min(a, b) ] 범위에서 두 수 모두의 약수가 되는 값들을 찾아 그 중 최대값을 구하는 방법을 생각해 볼 수 있습니다. 이를 코드로 구현하면 아래와 같습니다.
int get_gcd(int a,int b)
{
int max_div = 1; //가장 큰 공약수를 저장할 변수
int range = min(a, b);//두 수 중 작은 값 까지만 조사
for(int i=1; i<=range; i++)
{ //i부터 공약수를 찾는다.
if( a % i == 0 && b % i == 0)
{ // 두 수 모두의 약수일 경우
max_div = i; //갱신 (i는 점점 증가하므로)
}
}
return max_div;
}위의 알고리즘은 두 정수 a, b에 대하여 O( min(a,b) )의 시간복잡도를 가지게 됩니다. 어떻게 하면 조금 더 빠른 방법을 찾을 수 있을까요?
조금 잔머리를 굴려봅시다. 위의 알고리즘은 1부터 range까지 공약수를 찾아 그 중 마지막에 발견한 공약수를 반환합니다. 그렇다면 range부터 1까지 역순으로 탐색하여 가장 처음 발견된 공약수가 결국 최대 공약수가 됨을 알 수 있습니다.
int get_gcd(int a,int b)
{
int max_div = 1; //가장 큰 공약수를 저장할 변수
int range = min(a, b);//두 수 중 작은 값 까지만 조사
for(int i=range; i>=1; i--)
{ //i부터 공약수를 찾는다.
if( a % i == 0 && b % i == 0)
{ // 두 수 모두의 약수일 경우
max_div = i; //저장 후 탈출
break; //i는 점점 감소하므로, 더이상 볼 필요가 없다.
}
}
return max_div;
}이 방법을 사용하면 조금 더 빠를 것 같습니다. 하지만 이 알고리즘의 경우도 결국엔 a와 b가 서로소인 경우에는 모든 수를 검사하게 되므로, 위의 알고리즘과 똑같은 시간복잡도를 가집니다.
빠르게 최대공약수를 계산하는 알고리즘인 유클리드 호제법에 대해서 알아봅시다.
유클리드 호제법의 구현 - O(log(max(a,b)))
유클리드 호제법 알고리즘을 사용하면 최대 공약수를 빠르게 계산할 수 있습니다.
유클리드 호제법을 간략히 요약하면 아래와 같습니다.
f(a, b) = gcd(a, b)라 합시다. 이 때 a mod b = 0 이라면, f(a, b) = b임이 자명함을 알 수 있습니다. 이 때 a mod b이 0이 아닌 경우, f(a, b) = f(b, a mod b)가 성립하고, 이를 유클리드 호제법이라고 합니다.
두 정수 a와 b에 대하여 예를 들어봅시다. f(18, 12)의 경우 18 mod 12 = 6이므로, f(18, 12) = f(12, 6)이 성립합니다. 이 때 12 mod 6 = 0이 성립하므로 f(18, 12) = f(12, 6) = gcd(12, 6) = 6 이 성립합니다.
유클리드 호제법은 다양한 방식으로 구현할 수 있습니다. 아래의 방식 중 편한 방식을 사용하시면 될 것 같습니다.
int gcd(int a,int b)
{ //반복문을 이용한 방법
int mod = a % b;
while(mod > 0)
{
a = b;
b = mod;
mod = a % b;
}
return b;
}
int gcd2(int a,int b)
{ //재귀 함수형
if( a % b == 0 )
return b;
else
return gcd2(b, a % b);
}
int gcd3(int a, int b)
{ //삼항 연산자 축약형
return (a % b == 0 ? b : gcd3(b,a%b));
}이러한 유클리드 호제법은 두 정수 a와 b에 대하여 근사적으로 O( log2(min(a, b)) ) 시간복잡도를 가지는 알고리즘입니다. 어떻게 이러한 시간 복잡도에 근사하는 지는 나머지 연산의 성질을 생각해보시면 이해하기 쉽습니다.
a mod b가 0이 아닌 경우, f(a, b) = f(b, a mod b)이 성립한다고 했습니다. 이 때 a mod b라는 값은 [0, b-1]이라는 범위를 가지게 되며, 평균적으로는 해당 범위의 중간값을 가지게 됨을 알 수 있습니다. 이 처럼 매 번 f의 재귀식으로 이어질 때 마다 나머지 연산을 통해 수의 범위가 줄어들며, 그 범위는 평균적으로 전 범위의 절반에 해당하게 됩니다. 위 과정을 통해 통계적으로 탐색하는 수 범위가 대략 절반씩으로 감소하여 위의 시간 복잡도를 근사하게 가질 수 있게 됩니다.
단 위의 설명은 이해를 돕기위해서 한 대략적인 설명입니다.
또한 유클리드 호제법 알고리즘은 a와 b중 큰 수를 표현하기 위한 비트 수 n에 대해 Θ(n)회의 나눗셈으로 최대공약수를 구할 수 있다. 라고 알려져 있으며, 증명 방법은 찾아보시면 공부가 될 것 같습니다.
https://edu.goorm.io/learn/lecture/554/알고리즘-문제해결기법-입문
코딩테스트를 준비한다면?
