[ps] 코딩 테스트에 필요한 수학

나머지 연산

문제에서 결과 값이 너무 커지는 경우에 표현할 수 있는 자료형의 크기를 벗어나고 오버 플로우가 발생하기 때문에 나머지 연산을 수행한다. 보통 경우의 수를 구하는 문제에서 적용되는 경우가 많다.

• 두 수를 더한 후, M으로 나머지 연산을 수행하는 것은 두 수를 M으로 나머지 연산을 수행한 값을 더한 후, M으로 나머지 연산을 수행하는 것과 같다.
  (A + B) % M = (A % M + B % M) % M
• 두 수를 곱한 후, M으로 나머지 연산을 수행하는 것은 두 수를 M으로 나머지 연산을 수행한 값을 곱한 후, M으로 나머지 연산을 수행하는 것과 같다.
  (A x B) % M = (A % M x B % M) % M
• 두 수를 뺀 후, M으로 나머지 연산을 수행하는 것은 두 수를 M으로 나머지 연산을 수행한 값을 뺀 후, M으로 나머지 연산을 수행하는 것과 같다.
  (A - B) % M = (A % M - B % M + M) % M
  하지만 음수를 나머지 연산을 하는 경우 다른 값이 나올 수 있기 때문에 M을 더해서 양수로 만들어준다.
  0 <= A % M, B % M < M (두 수 A, B가 양수인 경우)
  -M <= A % M - B % M < M
  0 <= A % M - B % M + M < 2M
  M을 더하더라도 M의 나머지 연산의 결과 값은 동일하므로 음수인 경우에도 동일한 값을 구할 수 있다.

예제

https://www.acmicpc.net/problem/4375

2와 5로 나누어 떨어지지 않는 정수 N(1 <= N <= 10000)가 주어졌을 때, 1로만 이루어진 N의 배수 중 가장 작은 수의 자리 수를 구한다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        ) {
            String line;
            while ((line = reader.readLine()) != null) {
                int n = Integer.parseInt(line);
                int number = 0;
                for (int i = 1; ; i++) {
                    number = number * 10 + 1;
                    number %= n;
                    if (number % n == 0) {
                        writer.write(i + "");
                        writer.newLine();
                        break;
                    }
                }

            }
        }
    }

}

1로만 이루어진 수가 1 11 111 1111 ... 111111111 처럼 계속해서 커지는 경우 수의 표현 범위를 벗어나게 된다. 이 문제는 현재의 결과 값을 이전의 결과 값을 통해 구할 수 있다.

수	식
1	1 % N
11	(1 x 10 + 1) % N
111	(11 x 10 + 1) % N
1111	(111 x 10 + 1) % N
11111	(1111 x 10 + 1) % N

1로 이루어진 수가 계속 커질 수 있기 때문에 식의 일부를 먼저 나머지 연산을 수행하고 전체 연산을 수행해도 값이 동일한 나머지 연산의 특성을 사용하여 먼저 N의 나머지 연산 결과 값을 구한 후, 다른 연산을 수행하고 나머지 연산을 수행해서 결과 값을 구한다.

수	식
1	1 % N
11	((1 % N) x 10 + 1) % N
111	((11 % N) x 10 + 1) % N
1111	((111 % N) x 10 + 1) % N
11111	((1111 % N) x 10 + 1) % N

이전 문제의 결과 값인 나머지 연산의 결과 값을 사용하여 현재 문제를 해결할 수 있기 때문에 실제로 1로 이루어진 수를 표현하지 않아도 문제를 해결할 수 있다.

약수

두 자연수 A, B가 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. C가 A의 약수라면 A/C도 A의 약수가 되어야 한다. C = A/C인 경우는 A = C${^2}$이다.

24의 약수 1, 2, 3, 4, 6, 8, 12, 24

• 24 / 1 = 24
• 24 / 2 = 12
• 24 / 3 = 8
• 24 / 4 = 6

25의 약수 1, 5, 25

• 25 / 1 = 25
• 25 / 5 = 5 = $\sqrt 25$

약수를 구하는 가장 간단한 방법 중 하나는 N을 1부터 N까지의 수로 나누면서 나누어떨어지는 수를 구하는 것이다. 시간 복잡도는 O(N)이다.

for (int i = 1; i <= n; i++) {
	if (n % i == 0) {
    		// i는 n의 약수
   	}
}

약수의 대칭 특성을 사용하여 구하는 방법은 N을 1부터 $\sqrt N$까지의 수로 나누면서 나누어떨어지는 수를 구하고 N을 약수로 나누어 나머지 약수들을 구하는 것이다. 시간 복잡도는 O($\sqrt N$)이다.

for (int i = 1; i * i <= n; i++) {
	if (n % i == 0) {
    		// i는 n의 약수
    		if (i * i != n) {
        		// n / i는 n의 약수		
       		}
   	}
}

예제

https://www.acmicpc.net/problem/1037

어떤 수 N의 약수 중 1과 N을 제외한 모든 약수들이 주어졌을 때, N을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int count = Integer.parseInt(reader.readLine());
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

            int[] array = new int[count];

            for (int i = 0; i < count; i++) {
                array[i] = Integer.parseInt(tokenizer.nextToken());
            }

            Arrays.sort(array);
            System.out.println(array[0] * array[array.length - 1]);
        }
    }

}

약수들이 작은 수 부터 들어온다는 보장이 없기 때문에 모든 약수들을 배열에 저장 후, 정렬을 수행하고 가장 작은수와 가장 큰수를 곱해서 N을 구한다.

https://www.acmicpc.net/problem/17427

자연수 A의 모든 약수의 합은 f(A)이고 x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N(1이상 1000000이하)이 주어질 때, g(N)을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(reader.readLine());
            long sum = 0;

            for (int i = 1; i <= n; i++) {
                sum += (long) n / i * i;
            }

            System.out.println(sum);
        }
    }

}

이 문제의 시간 제한은 0.5초이다. 일반적인 방법으로 약수를 구하는 경우 f(A)의 시간 복잡도는 모든 약수를 구하는 시간 복잡도와 동일하므로 O($\sqrt N$)이다. g(N)의 시간 복잡도는 f(A)연산을 N만큼 수행하므로 O(N $\sqrt N$)이다.
문제의 조건상 N은 최대 1000000이 될 수 있는데 1000000 x $\sqrt 1000000$은 1000000000이므로 시간 복잡도 O(100000000)이 대략적으로 1초의 수행 시간이 걸린다고 했을 때, 일반적인 약수 방식으로 문제를 해결하는 경우 대략 10초의 수행 시간이 걸리므로 시간 제한에 걸리게 된다.
N이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 $\lfloor N / i \rfloor$이다. 즉, i를 약수의 합으로 i x $\lfloor N / i \rfloor$ 만큼 가진다는 것이다. 1부터 N까지의 수를 N이하의 자연수 중에서 가지는 약수의 합을 구해서 모두 더한 값은 g(N)과 동일하다. 시간 복잡도는 O(N)이다.

https://www.acmicpc.net/problem/17425

위 문제와 동일하게 자연수 N(1이상 1000000이하)이 주어질 때, 테스트 케이스 개수 T(1이상 100000이하)를 입력받아 g(N)을 입력받은 개수만큼 구한다.

import java.io.*;
import java.util.Arrays;

public class Main {

    public static int MAX = 1000000;

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            long[] f = new long[MAX + 1];
            long[] g = new long[MAX + 1];

            Arrays.fill(f, 1);

            for (int i = 2; i <= MAX; i++) {
                for (int j = 1; i * j <= MAX; j++) {
                    f[i * j] += i;
                }
            }

            for (int i = 1; i <= MAX; i++) {
                g[i] = g[i - 1] + f[i];
            }

            int count = Integer.parseInt(reader.readLine());

            for (int i = 0; i < count; i++) {
                int n = Integer.parseInt(reader.readLine());
                writer.write(g[n] + "\n");
            }
        }
    }

}

이 문제의 시간제한은 1초이다. 위의 문제에서 시간 복잡도 O(N)으로 문제를 해결할 수 있었지만 문제의 조건상 N은 최대 1000000이 될 수 있고 T는 최대 100000이 될 수 있는데 1000000 x 100000은 100000000000이므로 시간 복잡도 O(100000000)이 대략적으로 1초의 수행 시간이 걸린다고 했을 때, 최대 테스트 케이스 기준으로 대략 1000초의 수행 시간이 걸리므로 시간 제한에 걸리게 된다.
수행 시간이 길어지게되는 이유는 테스트 케이스마다 매번 f(A), g(x)를 새로 구하기 때문이다. 마찬가지로 약수의 반대는 배수라는 점을 이용하여 최대 N을 기준으로 모든 f(A)와 g(N)을 단 한번만 구하도록 한다.
f(A)를 구하는 연산의 시간 복잡도는 i가 2부터 N까지 증가함에 따라 총 N/2 + N/3 + ... N/N - 1 + N/N 만큼 연산을 수행하기 때문에 시간 복잡도는 O(N log${_2}^{N}$)이다. g(x)를 구하는 연산의 시간 복잡도는 O(N)이다. 입력받은 테스트 케이스의 갯수만큼 출력하는 시간 복잡도는 O(T)이다. 문제의 총 시간 복잡도는 O(N log${_2}^{N}$ + T)이다.

최대공약수, 최소공배수

최대공약수(GCD)는 두 수 A, B의 공통된 약수 중에서 가장 큰 정수이다. 최소공배수(LCM)는 두 수의 공통된 배수 중에서 가장 작은 정수이다. 최대공약수가 1인 두 수를 서로소라고 한다.

최대공약수를 구하는 가장 간단한 방법은 2부터 A, B 중 최소값까지 모든 정수로 나누면서 나누어떨어지는 수 중에서 가장 큰 수를 구하는 것이다. 시간 복잡도는 O(N)이다.

int g = 1;
for (int i = 2; i < Math.min(a, b); i++) {
	if (a % i == 0 && b % i == 0) {
		g = i;	
	}
}

최대공약수를 더 빠른 방법으로 구하는 방법은 유클리드 호제법이다. 시간 복잡도는 O(log ${_2}^{N}$)이다.

• a % b = r인 경우
• GCD(a, b) = GCD(b, r)이라는 성질을 사용한다.
• r이 0일 때 b의 값이 최대공약수이다.
• 세 수의 최대공약수는 마찬가지로 GCD(GCD(a, b), c)이다.

int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

최소공배수는 최대 공약수를 응용해서 구할 수 있다. LCM(A, B) = G x A/G x B/G이다.

int lcm(int a, int b) {
	int g = gcd(a, b);
	return g * (a / g) * (b / g);
}

소수

약수가 1과 자기 자신 밖에 없는 수이다. N의 약수가 1과 N밖에 없다면 소수이다.

소수 여부를 확인하는 방법은 약수의 대칭 성질을 이용하여 2부터 $\sqrt N$까지의 모든 정수로 나누면서 나누어떨어지는 없는 수를 구하는 것이다. 시간 복잡도는 O($\sqrt N$)이다.

boolean prime(int n) {
	if (n > 2) {
		return false;
	}
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

N이하의 모든 소수를 위의 방법을 여러번 하는 것 보다 더 빠른 방법으로 구하는 방법은 에라토스테네스의 체이다. 시간 복잡도는 O(N log log N)이다.

• 2부터 N까지의 모든 수를 써놓는다.
• 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
• 아직 지워지지 않은 그 수는 소수이다.
• 그 수의 배수를 모두 지운다.
• 배 수를 지우는 과정에서 어떤 수의 제곱부터 지워나가면 된다. 5 x 2는 2 x 5에서 이미 지워지고 5 x 3은 3 x 5에서 이미 지워지고 5 x 4는 2 x 10에서 이미 지워지므로 제곱 이하의 수는 이미 지워짐을 보장하기 때문이다.
• 즉, 어떤 수의 제곱이 N을 넘어가게 된다면 이미 소수가 아닌 수는 전부 지워졌음을 의미한다.

int n = 100;
boolean[] check = new boolean[n + 1];
check[0] = check[1] = true;
for (int i = 2; i * i <= n; i++) {
	if (!check[j]) {
		for (int j = i + i; j <= n; j += i) {
			check[j] = true;
		}
	}
}
for (int i = 0; i < n; i++) {
	if (!check[i]) {
		// 소수
	}
}

다음은 소수와 관련된 골드바흐의 추측이다.

• 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
• 위의 문장에 3을 더하면 2 + 3 = 5, 짝수 + 3 = 홀수, 두 소수 & 3(소수) = 세 소수
• 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
• 아직 모든 범위가 증명되지 않았지만 10$^{18}$이하 에서는 증명되어 있다.

예제

https://www.acmicpc.net/problem/6588

짝수 정수 N(6이상 1000000이하)가 100000개이하 만큼 주어질 때 각 테스트 케이스에 대해서 N = 홀수 소수 a + 홀수 소수 b 형태로 출력한다. 만약 N을 만들 수 있는 방법이 여러 가지라면 b - a가 가장 큰 것을 구한다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = 1000000;
            boolean[] check = new boolean[n + 1];
            check[0] = check[1] = true;

            for (int i = 2; i * i <= n; i++) {
                if (!check[i]) {
                    if (i % 2 == 0) {
                        check[i] = true;
                    }
                    for (int j = i * i; j <= n; j += i) {
                        check[j] = true;
                    }
                }
            }

            int number;
            while ((number = Integer.parseInt(reader.readLine())) != 0) {
                int i = 3;
                while (check[i] || check[number - i]) {
                    i += 2;
                }
                writer.write(number + " = " + i + " + " + (number - i) + "\n");
            }
        }
    }

}

N = a + b를 구성하는 두 수가 모두 홀수라는 조건이 있기 때문에 짝수 소수는 제외하면서 에라토스테네스의 체를 통해 모든 홀수 소수를 구한 후, b - a가 가장 큰 경우부터 찾기 위해 a를 가장 작은 홀수 소수인 3부터 증가시켜 a와 b가 모두 소수이면서 조건을 만족시키는 경우를 구한다.