- 우리는 보통 연산을 10진수 단위로(0,1,2,...)로 하지만, 컴퓨터는 이를 2진수로(0,01,0101,...) 처리한다. 이때 컴퓨터의 2진 연산을 처리하도록 하는 것이 비트 연산자이다.
- 두 bit(0 or 1)이 있을 때, and(&), or(|), xor(^), shift(>>, <<) 등의 비트연산자가 존재한다. 이러한 비트 연산자를 사용해 여러 유용한 계산 방식을 쓸 수 있다.
- i번째 bit를 1로 만들기
bit |= (1<<i);- i번째 bit를 0으로 만들기
bit &= ~(1<<i);- i번째 bit를 toggle(0 > 1, 1 > 0)
bit ^= (1<<i);- 최하위 i개의 bit를 모두 1로 만들기
bit |= (1 << i) - 1;- 모든 bit 0으로 만들기
bit = 0;
- 최대공약수(GCD, Greatest Common Divisor)는 두 수를 공통으로 나눌 수 있는 최대의 정수를, 최소공배수는 두 수의 배수가 되는 최소의 정수이다.
- 최대공약수 계산의 경우, 유클리드 호제법과 재귀함수를 이용하여 구현할 수 있다.
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}- 임의의 수 A, B의 최대공약수가 G라면, A=aG, B=bG로 표현할 수 있다고 할 때,
- (a - kb)G = c 형태로 관계식을 나타낼 수 있다. 이때 a-kb와 b의 최대공약수가 G이기 위해 두 수는 서로소여야 하고, 이 조건을 만족할 때 b와 c의 최대공약수는 G가 된다.
- 위의 재귀 코드는 다음과 같이 동작한다.
- 먼저 a, b를 받아서, b의 값이 참인지를 (= 존재하는지) 확인한다. (약수 계산이므로 a, b는 모두 2 이상임을 가정한다.)
- gcd는 b와 a/b의 나머지를 매개변수로 받아 gcd 함수를 다시 호출한다.
- 이 과정을 반복할 때 두 수 사이의 공통된 약수가 있다면, gcd(a,b)함수의 b에는 언젠가 0이 전달된다.
- b=0이 전달되는 시점에서 해당 함수에 전달된 a값이 최대공약수로 반환되게 된다.
- 만약 두 수가 서로소라면(ex. 2, 3), 마지막에는 a%b에 1이 전달될 것이므로, 최소공배수가 1이 전달된다.
- 두 수 a, b의 최소공배수는 a * b / G로 계산 가능하다.
int g = gcd(a, b);
int lcm = a * b / g;
//오버플로우 방지
int g = gcd(a, b);
int lcm = a / g * b / g * g;위 코드로 간편히 풀 수 있지만, 곱셈 연산은 오버플로우의 우려가 있으므로, 경우에 따라 아래 코드로 계산할 수 있다.
- 소수 : 1과 자기 자신으로만 나누어 떨어지는 수 (ex. 2, 3, 5, 7, 11, ...)
- 소수의 판별
- 임의의 수 N이 있을 때, 2부터 N-1까지 모두 나누어 나머지가 0인 경우가 있는지 판별하면 된다. 이때 하나라도 거짓인 경우 소수가 아니다.
- 여기서 계산을 조금 줄인다면, N의 제곱근까지만 연산해도 된다( 그 수를 제곱했을 때 나누어 떨어지면 소수가 아닐테니까 )
#include <iostream>
using namespace std;
int main(void)
{
bool prime = true;
int n;
cin >> n;
for(int i=2 ; i * i <= n; i++)
{
if(num % i == 0){
cout << "소수가 아닙니다";
return 0;
}
}
cout << "소수입니다";
return 0;
}- 위에서 1부터 루트 n까지 비교하면 된다고 했지만, 제곱근을 구하는 연산은 많은 자원을 필요하기 때문에, 반대로 제곱이 입력받은 수가 되는가를 비교하여 소수를 판별하게 한다.
- 에라토스테네스의 체는 특정 범위의 수가 소수인지 아닌지를 판별하는 방법을 말한다.
- 일단 0, 1은 고정적으로 소수가 아니고, 2부터 시작해서 2의 배수, 3의 배수를 계속해서 지워나가는 식으로 연산을 하면 된다.
#include <iostream>
using namespace std;
#define MAX 100000
int main(void)
{
bool arr[MAX] = {1, 1}
for(int i=2;i * i <= MAX;i++}
{
if(arr[i]) continue; //배열 값이 1이면(true - 소수가 아니다) 패스한다.
for( int j = i * i; j < MAX ; j += i ) arr[j] = 1;
}
return 0;
}- 이때 이중 for문 j가 i의 제곱부터 시작하는 이유는, 그 전의 수는 계산 과정에서 이미 소수 여부가 판별이 되었기 때문이다.
- 예를 들어 i=2일 때, 이미 2의 배수는 모두 지워진 상태이다. 즉 i=3이 되었을 때, 3*1은 자명하게 소수인 상태이고, 3*2는 2의 배수 연산 때 이미 소수임이 판별되었으므로 연산할 필요가 없는 상태이다.
출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)