https://www.acmicpc.net/problem/1929
백준(BOJ) 사이트에 들어간 게 정말 오랜만이네요.
최근에 바쁘다는 핑계로 알고리즘 문제 풀이에서 많이 멀어졌던 것 같습니다.
이제부터라도 하루에 한 문제씩 가벼운 문제를 풀고,
일주일에 한 번씩은 좀 더 복잡한 알고리즘 문제도 도전해서 감을 잃지 않도록 꾸준히 유지해보려고 해요.
물론 매일같이 문제를 푸는 게 쉽지는 않겠지만, 틈틈이 하루에 한 문제씩 일반 문제를 풀고 ,
일주일에 한 문제씩 알고리즘 문제를 풀어볼려고 목표를 설정했습니다.
문제 설명
- 문제
M이상 N이하의 소수를 모두 찾아서 출력해야 합니다. - 입력
- 한 줄에 자연수 M과 N이 주어집니다. (1 ≤ M ≤ N ≤ 1,000,000)
- M 이상 N 이하의 소수가 하나 이상 존재하는 입력만 주어집니다.
- 출력
- M 이상 N 이하의 소수를 오름차순으로 한 줄에 하나씩 출력합니다.
예제
- 입력
3 16 - 출력
3 5 7 11 13
단순 반복(브루트포스)
처음에는 각 숫자가 소수인지 판별하는 메서드를 만들고 , M부터 N까지 전체를 검사하려고 했습니다.
x에 대하여 2부터 √x(x의 제곱근)까지 나눠보면서 한 번이라도 나누어떨어질 때 소수가 아니라고 판정하도록
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// M부터 N까지 순회하며 isPrime 판별
StringBuilder sb = new StringBuilder();
for (int i = M; i <= N; i++) {
if (isPrime(i)) {
sb.append(i).append("\n");
}
}
System.out.print(sb);
}
// 소수 판별 메서드
private static boolean isPrime(int num) {
// 1은 소수가 아니므로 바로 false
if(num <= 1) {
return false;
}
// 2부터 sqrt(num)까지 나눠떨어지면 소수가 아님
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}- 작동 원리
- M부터 N까지 모든 숫자 i에 대해, isPrime(i)를 호출합니다.
- isPrime(i) 내부에서는 2부터 sqrt(i)까지 돌며 나누어떨어지는지 확인합니다.
- 시간 복잡도
- 최악의 경우 N−M+1N - M + 1개에 대해 각각 N\sqrt{N}까지 검사
- 대략 O((N−M+1)N)O((N-M+1)\sqrt{N})
- 결과: NN이 최대 1,000,000까지 가능하므로, 최악의 경우 1,000,000에 가까운 수를 검사해야 하고 각 수마다 최대 1,000번 정도(루트 1,000,000 ≈ 1000) 반복하게 됩니다. (문제는 풀 수 있었으나 , 시간이 오래걸리는 단점 )
"에라토스테네스의 체" - Algorithm
큰 범위에서 소수를 빠르게 구하는 대표적인 알고리즘은 에라토스테네스의 체(Sieve of Eratosthenes)입니다.
알고리즘 아이디어
- 2부터 시작해서, 어떤 수 i가 소수라고 판단되면 i의 배수들을 모두 소수가 아니라고 표시
- 그 다음 수로 넘어가서, 여전히 소수로 표시되어 있다면 또 그 배수를 지움
- 이를 반복하면, 결과적으로 소수가 아닌 숫자는 전부 필터링
시간 복잡도
- 에라토스테네스의 체는 대략 O(NloglogN)O(N \log \log N)의 시간 복잡도를 가집니다.
- NN이 1,000,000이라도 충분히 2초 내에 계산 가능하므로, 시간 초과를 해결할 수 있습니다.
에라토스테네스의 체 코드 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// 인덱스를 숫자로 보고 해당 숫자가 소수인지 여부를 저장할 배열
boolean[] isPrime = new boolean[N + 1];
// 2부터 N까지 일단 모두 소수(true)라고 가정 (단, 0과 1은 소수가 아니므로 제외)
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// 에라토스테네스의 체 : i가 소수라면, i의 배수들을 모두 소수가 아니라고 표시(false)
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// M 이상 N 이하인 소수만 출력
StringBuilder sb = new StringBuilder();
for (int i = M; i <= N; i++) {
if (isPrime[i]) {
sb.append(i).append("\n");
}
}
// 한꺼번에 결과 출력
System.out.print(sb);
}
}알고리즘 해설
- 소수 판별 배열(isPrime)
- boolean[] isPrime = new boolean[N + 1];
- i번 인덱스를 “숫자 i가 소수인가(true/false)”를 저장하는 용도로 사용
- 0과 1은 소수가 아니므로 제외, 2부터 true로 초기화합니다.
- 반복(for (int i = 2; i * i <= N; i++))
- i가 소수(true)인 경우, i*i부터 N까지 i 간격으로 뛰며 배수를 지웁니다.
- i*i 이전의 배수들은 이미 이전 단계에서 처리되었습니다.
- 출력
- M부터 N까지 순회하며 isPrime[i]가 true이면 출력합니다.
- 많이 쓰는 최적화 팁: StringBuilder를 활용하여 출력 성능을 향상시킵니다.
마무리
- 단순 반복(브루트포스) 접근:
- 작은 범위에는 충분히 빠르지만, 최대 1,000,000까지 가면 비효율적
- 각 수마다 최대 N\sqrt{N} 반복이 커서 비효율적.
- 에라토스테네스의 체:
- O(NloglogN)O(N \log \log N) 알고리즘으로, 1,000,000 범위도 2초 내에 가능.
- "한 번에 대량의 소수를 구하는" 상황에 최적화된 방법.
이렇게 시간 초과를 경험한 뒤, 에라토스테네스의 체로 알고리즘을 변경해서 문제를 해결할 수 있습니다.
소수 문제는 거의 항상 에라토스테네스의 체를 먼저 떠올리면 좋을 것 같습니다.
범위가 큰 경우, 단순 반복으로는 시간 초과가 날 가능성이 매우 큽니다.
