[알고리즘] 알고리즘 뽀개기(3) : 수학

알고리즘 뽀개기 Step 3 : 수학

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.

수학

나머지 연산

컴퓨터의 정수는 저장할 수 있는 범위가 저장되어있기에, 답을 M으로 나눈 나머지를 출력하라는 문제가 종종 등장한다.

• (A + B) mod M = ((A mod M) + (B mod M)) mod M
• (A X B) mod M = ((A mod M) X (B mod M)) mod M
• (A - B) mod M = ((A mod M) - (B mod M) + M) mod M
  • 뺄셈의 경우는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 위와 같이 M을 더한후 mod 를 수행한다.

최대 공약수 / 최소 공배수

최대 공약수

최대 공약수는 줄여서 GCD 라고 부르기도 한다.
두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중, 가장 큰 정수이다.

• 최대 공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B) (A와 B 중 작은 수)까지 모든 정수로 나누어 공통된 약수인지 확인해 보고 그 중 가장 큰 약수를 찾는 방법이다.
• 최대 공약수가 1인 두 수를 서로소(Coprime)이라고 한다.

최소 공배수

최소공배수는 줄여서 LCM 이라고 부르기도 한다.
두 수의 최소공배수는 두 수의 공통된 배수 중, 가장 작은 정수이다.

• 최소공배수는 GCD를 응용해 구할 수 있다.
  • 두 수 a,b의 최대 공약수인 G를 구하면 최소 공배수 L은 G_(a/G)_(B/G)이다.

진법 변환

10진법 수인 N을 B진법으로 바꾸려면 N이 0이 될때 까지 나머지를 계속해서 구한다.

• 16을 3진법으로 바꾸기
  • 16/3 = 5...1
  • 5/3 = 1...2
  • 1/3 = 0...1
  • 따라서, 16은 3진법으로 121이다. (9 + 6 + 1 = 16)

소수

• 소수는 약수가 1과 자기 자신 뿐인 수이다.
• N이 소수일 경우, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• N이 소수일 경우, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
  • N의 약수 중, 가장 큰 것은 N/2보다 작거나 같기 때문이다.
    • N = a X b 로 나타낼 수 있는데, a 가 작을수록 b가 크다.
    • 가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2 를 넘지 않는다.
• N이 소수일 경우, 2보다 크거나 같고, 루트N보다 작거나 같은 수로 나누어 떨어지면 안된다.
  • N이 소수가 아니라면, N = a X b 로 나타낼 수 있다. (a <= b)
  • 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다. (차이가 없음)
  • 따라서, 루트 N까지만 검사해보면 된다.
    for(int i = 2; i*i <=n; i++)
• 시간 복잡도는 O(루트 N)이 된다.

에라토스테네스의 체

• 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

1. 2부터 N까지 모든 수를 써놓는다.
2. 아직 지워지지 않은 수 중, 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 그 수의 배수를 모두 지운다.

1부터 N까지 모든 소수를 구하는 것이 1차적인 목표이기 때문에, 구현할 때 바깥 for문 i를 N까지 돌린다.
안쪽 for문 j는 N의 크기에 따라 i_i 혹은 i_2 로 바꾸는 것으로 정수형 범위를 고려한다.

골드바흐의 추측

• 2보다 큰 모든 짝수는 두 소수의 합으로 표현이 가능하다.
• 위 문장에 다음으로 큰 소수인 3을 더하면, 아래와 같은 표현이 가능하다.
• 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
• 10^18 이하에서는 참인 것이 증명되어있으나, 그 이상은 증명되지 않았다.

소인수분해

• 정수 N을 소수의 곱으로 분해한다.
• N을 소인수분해했을 때, 나타날 수 있는 인수 중, 가장 큰 값은 루트 N이다.
• 2부터 루트 N까지 for문을 돌면서, N을 나눌 수 있으면 나누며 나아간다.

for(int i = 2; i*i <=n; i++) {
    while(n%i == 0) {
        printf("%d\n", i);
        n /= i;
    }
}
if(n > 1) {
    printf("%d\n", n);
}

팩토리얼

N! = 1 x 2 x ... x N
팩토리얼은 매우 큰 값이다.

아래 복습 문제와 함께 알아보도록 하자.

복습 문제

팩토리얼 0의 개수 (1676번)

• https://www.acmicpc.net/problem/1676
• N! = 1 x 2 x ... x N 의 결과값에서 0이 몇개인지 알아내는 문제이다.
• 10! = 3628800 으로, 0의 개수가 2개인데, 이는 10!을 소인수분해하면 알 수 있다.
• 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10
• 10!을 소인수분해 했을 때, 2와 5가 몇개 나오는지 알아야한다. 5의 개수가 항상 2의 개수보다 적기 때문에, 5의 개수만 세어준다.

• 100/5를 했을 때, 20개
• 100/25를 했을 때, 4개
• 따라서, 5의 개수는 24개이다. 따라서, 0의 개수는 24개이다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()

    var result : Int = 0
    var num = 5;
    while(num <= N) {
        result += (N/num)
        num *= 5
    }

    println(result)
}

소수 구하기 (1929번)

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val M = input[0].toInt()
    val N = input[1].toInt()

    val primeArr = BooleanArray(1000001) {true}
    primeArr[0] = false
    primeArr[1] = false

    for(i in 2..N) {
        if (!primeArr[i]) continue

        var j = 2
        while(i * j <= N) {
            primeArr[i * j] = false
            j++
        }
    }

    for(i in M..N) {
        if (primeArr[i]) {
            println(i)
        }
    }
}