수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻한다. 실제 코딩 테스트에서는 모든 정수론의 분야가 나오지 않고, 영역도 매우 방대하므로 전체를 공부하기에는 효율성이 떨어진다. 따라서 여기서는 소수 부분과 호제법 부분을 집중적으로 다루도록 하겠다.
소수 구하기
소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.
소수 구하기의 핵심 이론
소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 원리는 다음과 같다.
1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수를 출력한다.
위의 움짤을 보면 바로 이해할 수 있다.
일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다. 이러한 이유 때문에 에라토스테네스의 체 기법은 현재에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용되고 있다.
[백준 1929번] 소수 구하기
https://www.acmicpc.net/problem/1929
숫자 사이에 소수를 출력하는 문제이다. N의 최대 범위가 1,000,000이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간 초과가 발생한다. 따라서 앞의 배운 에라토스테네스 방법으로 문제를 풀어야 한다. 참고로 일반적으로 소수를 찾을 때는 2 이상부터 자기 자신보다 작은 수로 나눴을 때 나머지가 0이 아닌 수를 찾는다.
1. 크기가 N + 1 인 배열을 선언한 후 값은 각각의 인덱스 값으로 채운다.
2. 1은 소수가 아니므로 삭제한다.
3. 2부터 N의 제곱근까지 값을 탐색한다. 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경한다.
4. 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력한다.
N의 제곱근까지만 탐색하는 이유
N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 만약 16의 범위까지 소수를 구할 때 16 = 4 * 4 로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻이다. 따라서 4까지만 확인하고 소수 판별을 진행하면 된다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
int[] A = new int[N+1];
for (int i = 2; i <= N; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(N); i++) { // 제곱근까지만 수행하기
if(A[i] == 0) continue;
for (int j = i + i; j <= N; j = j + i) { // 배수 지우기
A[j] = 0;
}
}
for (int i = M; i <= N; i++) {
if(A[i] != 0)
System.out.println(A[i]);
}
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
boolean[] notPrime = new boolean[N+1];
notPrime[1] = true;
for (int i = 2; i <= N; i++) {
if(notPrime[i]) continue;
for (int j = 2; i*j <= N; j++) {
notPrime[i*j] = true;
}
}
for (int i = M; i <= N; i++) {
if(!notPrime[i])
System.out.println(i);
}
}
}
[백준 1456번] 거의 소수
https://www.acmicpc.net/problem/1456
최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다. 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 소수를 탐색해야 한다. 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구한다. 그 이후에는 주어진 소수들이 A ~ B 범위 안에 존재하는지 판별해 유효한 소수의 개수를 세면 문제를 해결할 수 있다.
1. 2 ~ 10,000,000 사이에 존재하는 모든 소수를 구한다.
2. 각각의 소수에 관해 소수를 N제곱한 값이 B보다 커질 때까지 반복문을 실행한다. 이때 소수를 N제곱한 값이 A보다 크거나 같으면 거의 소수로 판단해 카운트한다. 모든 소수에 관해서는 반복문을 실행한 후 카운트한 값을 출력한다.
이 부분을 실제 구현하면 N제곱한 값을 구하는 도중 값의 범위가 long형을 초과하는 경우가 발생한다. 따라서 계산 오류를 방지하려면 N^k과 B 값이 아니라 N과 B / N^k-1 을 비교하는 형식으로 식을 적절하게 정리해야 한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
long A = sc.nextLong();
long B = sc.nextLong();
long[] arr = new long[10000001];
for (int i = 2; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 2; i <= Math.sqrt(arr.length); i++) { // 제곱근까지만 수행하기
if(arr[i] == 0) continue;
for (int j = i + i; j < arr.length; j = j + i) { // 배수 지우기
arr[j] = 0;
}
}
int count = 0;
for (int i = 2; i < 10000001; i++) {
if(arr[i] != 0) {
long tmp = arr[i];
while((double)arr[i] <= (double) B/(double) tmp) {
if((double)arr[i] >= (double) A/(double) tmp) {
count++;
}
tmp *= arr[i];
}
}
}
System.out.println(count);
}
}
여기서 자세히 봐야 할 부분은 소수의 제곱 수가 B보다 작을 때까지만 반복하는 부분이다. 그냥 무작정 끝까지 제곱해보고 그 값이 A ~ B의 범위 안인지 확인하는 방식으로 하면 시간초과가 난다. 또한 long 형의 범위를 넘어 잘못된 결과가 나올 수 있으므로 arr[i] * tmp <= B 를 확인하는 대신 arr[i] <= B / tmp 를 계산해 확인한다. arr[i] >= A / tmp 부분도 마찬가지. 수가 커지는 경우 이러한 계산 방식을 잘 기억하자!
[백준 1747번] 소수&팰린드롬
https://www.acmicpc.net/problem/1747
에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다. 앞에서 배웠던 두 문제와 매우 비슷하므로 답을 쉽게 구할 수 있을 것이다. 단, 팰린드롬 수를 판별할 때 Integer 값의 적절한 형 변환을 이용해 좀 더 쉽게 구할 수 있는 로직이 문제를 해결하는 데 도움이 된다.
1. 2 ~ 10,000,000 사이에 존재하는 모든 소수를 구한다. 그 중 N보다 크거나 같은 소수에서 팰린드롬 수인지를 판별한다.
2. 소수의 값을 char 배열 형태로 변환한 후 양끝의 투 포인터를 비교하면 쉽게 팰린드롬 수인지 판별할 수 있다. 배열의 처음과 끝을 가리키는 포인터 (S, E)를 부여해 두 값을 비교하며 같으면 S++, E-- 연산으로 두 포인터를 이동한다. S < E를 만족할 때까지 반복해 모든 값이 같으면 팰린드롬 수로 판별한다.
3. 오름차순으로 과정 2를 실행하다가 최초로 팰린드롬 수가 나오면 프로그램을 종료한다.
나는 String 형으로 변환한 후 for 루프로 거꾸로 돌며 다른 String 형의 변수에 뒤집힌 형태의 문자열을 새로 만들었다. 둘이 같다면 true를 반환하도록 했는데 이렇게 했을 경우 String 변수가 계속 만들어지며 공간이 낭비되고 위의 방법으로 하면 절반의 시간밖에 걸리지 않으므로 잘 기억해두자. (투 포인터 배웠는데도 적용할 생각을 못했다)
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[10000001]; // N의 범위까지 소수 구하기
for (int i = 2; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 2; i < Math.sqrt(arr.length); i++) { // 제곱근까지만 수행
if(arr[i] == 0) continue;
for (int j = i * 2; j < arr.length; j += i) { // 배수 지우기
arr[j] = 0;
}
}
int i = N;
while (true) { // N부터 1씩 증가시키면서 소수와 팰린드롬 수가 맞는지 확인하기
if(arr[i] != 0) {
int result = arr[i];
if(isPalindrome(result)) {
System.out.println(result);
break;
}
}
i++;
}
}
static boolean isPalindrome(int target) { // 팰린드롬 수 판별 함수
char tmp[] = String.valueOf(target).toCharArray();
int s = 0;
int e = tmp.length - 1;
while (s < e) {
if(tmp[s] != tmp[e])
return false;
s++;
e--;
}
return true;
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[10000000];
for (int i = 2; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 2; i < Math.sqrt(arr.length); i++) {
if(arr[i] == 0) continue;
for (int j = i * 2; j < arr.length; j += i) {
arr[j] = 0;
}
}
for (int i = N; i < arr.length - N; i++) {
if(arr[i] != 0 && isPalindrome(Integer.toString(i))) {
System.out.println(i);
return;
}
}
}
static boolean isPalindrome(String str) {
String reverse = "";
for (int i = str.length()-1; i >= 0; i--) {
reverse += str.charAt(i);
}
return str.equals(reverse);
}
}
[백준 1016번] 제곱 ㄴㄴ 수
https://www.acmicpc.net/problem/1016
언뜻 보면 min의 최댓값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로는 min과 max 사이의 수들 안에서 구하는 것이므로 1,000,000의 데이터만 확인하면 된다. 제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스 체 알고리즘 방식을 제곱수 판별 로직에 적용해 문제를 해결해 보겠다.
1. 2의 제곱수인 4부터 max값까지 제곱수를 찾는다.
2. 탐색한 배열에서 제곱수로 확인되지 않은 수의 개수를 센 후 출력한다.
데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색해 시간 복잡도를 최소화하는 것이 이 문제 풀이의 핵심이다.
난 처음에 저 범위를 이해하지 못하고 그냥 너무 넓다고만 생각했다. 그러나 Max의 범위를 자세히 보면 min보다 크거나 같고, min에 1,000,000을 더한 것보다 작거나 같으므로 값만 크다 뿐이지 실질적 범위는 최대로 잡아봤자 백만 뿐이 되지 않는다. 그래서 체크해주는 배열의 크기 또한 (max-min+1)로 설정한 것이다. 제곱수들의 배수를 구하는 것도 마찬가지인데, 우리가 궁금한 건 min부터 max까지의 제곱수들과 그 배수이지, 그 외 다른 범위는 구할 필요가 없다. 배열에 들어가는 건 min~max 인덱스의 제곱 ㄴㄴ 수 체크인데, 값의 범위가 10^12가 넘어가므로 너무 크다. 그러나 범위 자체는 백만이므로 우리가 궁금한 값의 범위인 백만만 배열에 저장하면 되는 것이다. start_index는 만약 Min의 값이 10인데, 10미만의 제곱 ㄴㄴ수인 4와 9는 구할 필요가 없기 때문에 설정해 준다. 만약 4로 나눈다면 2가 나올테고, 나머지가 0이 아니므로 (나머지가 0이 아닌 경우는 더 작거나 크거나, 우린 큰 걸 구해야 하므로, (작다면 몫이 0이 나올테니 상관없음)) 1을 더해준다. 그럼 start_index가 3이 나오므로 4*3=12가 되어 10 이상의 제곱 ㄴㄴ 수를 바로 구할 수 있다. 인덱스로 넣어줄 때 Min을 빼는 것을 꼭 잊지 말자. 개념 자체는 앞의 것을 응용하면 되므로 어렵지 않지만 범위 구하고 생각하는게 정말.. 헷갈렸던 문제이다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
long Min = sc.nextLong();
long Max = sc.nextLong();
// 최댓값과 최솟값의 차이만큼 배열 선언
boolean[] check = new boolean[(int) (Max - Min + 1)];
// 2의 제곱수인 4부터 Max보다 작거나 같은 값까지 반복
for (long i = 2; i * i <= Max; i++) {
long pow = i * i; // 제곱수
long start_index = Min / pow;
if(Min % pow != 0)
start_index++; // 나머지가 있으면 1을 더해야 Min보다 큰 제곱수에서 시작됨
for (long j = start_index; pow * j <= Max; j++) { // 제곱수를 true로 변경하기
check[(int) ((j*pow) - Min)] = true;
}
}
int count = 0;
for (int i = 0; i <= Max - Min; i++) {
if(!check[i])
count++;
}
System.out.println(count);
}
}
참고 설명 : https://imksh.com/69
백준 1016 제곱ㄴㄴ수 풀이 Python
문제로이동 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱
imksh.com
[참고 자료]
- 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 정수론 - 유클리드 호제법 (0) | 2024.05.31 |
|---|---|
| 정수론 - 오일러 피 (0) | 2024.05.30 |
| 그리디 (0) | 2024.05.28 |
| 이진 탐색 (Binary Search) (0) | 2024.05.25 |
| 너비 우선 탐색 (BFS) (0) | 2024.05.24 |
