1. 수학 / 최대공약수, 최소공배수, 소수

나머지(모듈러) 연산

나머지 연산이 중요한 이유는 C의 int, Java의 long long처럼 최대 크기가 제한되어있는 자료형이 주어졌을 때, 결과값이 너무 클 경우 해당 자료형에 들어가지 못하기 때문이다. 이럴 경우에 나머지 연산을 이용하여 몫을 구하라는 내용이 문제에 포함되게 된다. 아래의 규칙을 잘 알아두자.

(A+B)%M = ((A%M)+(B+M))%M
(AxB)%M = ((A%M)x(B+M))%M
위의 규칙은 나누기일 경우에는 성립하지 않는다.

(A-B)%M = ((A%M)-(B%M)+M)%M
뺄셈의 경우에는 먼저 모듈러 연산을 한 결과가 음수일 수 있기 때문에, 위와같이 계산해야한다.

---

최대공약수(GCD)

• 일반적으로 최대공약수가 필요한 경우는 정답이 분수일 때, 기약분수의 형태로 나타낼 때이다.
• 최대공약수를 구하는 방법은 여러가지가 있으나, 가장 빠른 방법은 유클리드 호제법이다. (O(logN))
  • 유클리드 호제법: GCD(a, b) = GCD(b, r)에서 r=a%b일 때, r이 0이면 r은 a와 b의 최대공약수이다.

유클리드 호제법을 구현한 코드는 다음과 같다.

재귀를 사용하여 구현하는 경우

int gcd(int a, int b) {
  if(b==0) {
    return a; //b가 0이므로 a는 최대공약수가 된다.
  } else {
    return gcd(b, a%b);
  }
}

반복문을 사용하여 구현하는 경우

int gcd(int a, int b) {
  while(b!=0){
    int r = a%b;
    a=b;
    b=r;
  }
  return a; //루프가 종료되는 시점은 b가 0이므로, a는 최대공약수가 된다.
}

반복문을 쓰는 경우 변수를 하나 추가하긴 하지만, 여전히 복잡도는 O(logN)이다.

최대공약수(GCD)의 합, 백준 온라인 저지

---

최소공배수(LCM)

a와 b의 최대공약수를 g라고 할때, 최소공배수 l=(a*b)/g이다.

최소공배수(LCM), 백준 온라인 저지
최대공약수와 최소공배수, 백준 온라인 저지

소수(Prime Number)

소수와 관련된 문제는 보통 두 가지 경우가 있다. 자연수 N이 주어졌을 때, N이 소수인지 판별하거나, N이하의 자연수 중 소수를 찾는 문제이다.

자연수 N이 소수인지 판별하기

소수 N은 1과 자기 자신 이외의 수로는 나누어 떨어지지 않는 수이다. 이를 바꿔말하면, N은 2보다 크고, N-1 이하의 수로 나누어 떨어지지 않는 수를 말한다고 할 수 있다. 이를 코드로 나타내면 다음과 같다.

bool prime(int n) {
  //소수는 2 이상이므로, 2보다 작다면 n은 소수가 아니다.
  if(n<2) {return false;} 
  for(int i=2; i<=(n-1); i++) {
    //n-1보다 작은 수로 나누어 떨어진다면 n은 소수가 아니다.
    if(n%i==0) {return false;}
  }

 return true;
}

위 코드의 복잡도는 O(N)이다.

위의 코드는 다음의 조건에 의해 좀 더 최적화될 수 있다. 자연수 N=a*b로 표현할 수 있을 때, N이 소수가 아닐 경우 a의 최소값은 2가 된다. (a가 1일 경우에는 b가 N이 되므로, 소수의 조건이 되기 때문이다.) 따라서 N은 N/2보다 작거나 같은 자연수로 나누어떨어지면 안된다는 것을 알 수 있다. 이 조건을 위의 코드에 적용시키면, for 구문의 범위값만 달라지게 된다.

bool prime(int n) {
  //소수는 2 이상이므로, 2보다 작다면 n은 소수가 아니다.
  if(n<2) {return false;} 
  for(int i=2; i<=(n/2); i++) { //범위값이 절반으로 줄어들었다.
    //n-1보다 작은 수로 나누어 떨어진다면 n은 소수가 아니다.
    if(n%i==0) {return false;}
  }

 return true;
}

루프의 수가 N/2회로 줄어들긴 했지만, big-O 점근법에서 이는 여전히 O(N)이다.

위의 코드는 다음의 조건에 의해 좀 더 최적화될 수 있다. N=a*b를 만족할 때 a가 b보다 크다고 가정하면, a는 루트N보다 작고 b는 루트N보다 커야한다. 따라서 N이 소수라면 N은 2보다 크고, 루트N보다 작거나 같은 자연수로 나누어 떨어지면 안된다는 것을 알 수 있다. 다만 루트N은 실수이며, 실수는 근사값이므로 최대한 사용하지 않는게 좋다. 이런 경우 양변에 제곱을 취해줌으로써 해결할 수 있다. 이 조건을 적용한 코드는 다음과 같다.

bool prime(int n) {
    if(n<2) {return false;} //n이 2보다 작은 경우 소수가 아니다.
    for(int i=2; i\*i<=n; i++) { // i<=루트n 대신 양변에 제곱을 취하여, i\*i<=n이 된다.
      if(n%i==0) {return false;}
    }
    return true;
  }

위 코드의 복잡도는 O(루트N)이다.

소수 찾기, 백준 온라인 저지

자연수 N 이하의 수 중 소수 찾아내기 (에라토스테네스의 체)

에라토스테네스의 체는 다음의 규칙을 가진다.

1. 2부터 N까지의 모든 수를 써 놓는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 그 수는 소수이다.
3. 2에서 찾은 소수의 배수를 모두 지운다.
4. 2~3을 반복하고 남은 수는 모두 소수이다.

에라토스테네스의 체를 구현한 코드는 다음과 같다. 실제로 배열의 항목을 지우게되면 효율성이 떨어지기 때문에, boolean타입의 배열을 선언하여 소수인지 아닌지 여부만 기재한다.

int prime[100]; //소수를 저장하는 배열
int pn=0; //소수의 갯수 (루프문 내에서 index의 역할을 한다.)
bool check[101]; //지워진 경우 true. 배열의 전체값은 false로 초기화되었다고 가정한다.
int n=100; //n=100. 100까지의 소수를 구하는 코드다.

for(int i=2; i<=n; i++) {  
  if(check\[i\] == false) {  
    prime\[pn++\] = i; //아직 지워지지 않은 수 중에서 가장 작은 수는 소수이다.  
    // 소수의 배수를 모두 지운다.  
    for(int j=i\*i; j<=n; j+=i) {  
      check\[j\] = true;  
    }   
  }  
}  

안쪽 for문에서 j의 초기값은 N의 크기에 따라, i*i에서 i*2로 변경하는 것이 좋다. i값이 클 경우 int형의 범위를 넘어설 수 있기 때문이다.

소수 구하기, 백준 온라인 저지