728x90
※ 문제
1. 실패 코드(시간초과)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int start = 0;
int end = 0;
String numRange = scan.nextLine();
String[] strArr = numRange.split(" ");
start = Integer.parseInt(strArr[0]);
end = Integer.parseInt(strArr[1]);
for(int i=start; i<=end; i++) {
if(primeNumberSe(i)) System.out.println(i);
}
}
static boolean primeNumberSe(int number) {
if(number == 0 || number == 1) {
return false;
}
for(int i=2; i<number; i++) {
if(number % i ==0) {
return false;
}
}
return true;
}
}
※ 실패 분석
소수여부를 판독하기 위한 함수 'primeNumberSe'를 생성했다. 해당 로직은 소수가 될 수 있는 2~(자기자신-1)까지 나눈 경우 한 번이라도 나눠지면 소수인 것으로 false를 return해주는 함수이다. 백준에 제출했는데 시간초과로 실패했다.
그럴 것이 1~1,000,000까지의 숫자를 모두 구해주는 경우 시간복잡도는 O(n^m)의 가깝다.(정확하지 않음)
예를 들어, 작은 숫자의 소수판독은 빠르지만 999,999와 1,000,000 두 수만 판독해도 2~999.998 번 반복하고 2~999,999번 반복한다. 백준에서 제시한 시간 제한 2초를 넘을 수 밖에 없다.
2. 성공 코드(에라토스테네스의 체)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
boolean[] prime = new boolean[1000001];
prime[0] = prime[1] = true;
for(int i=2; i*i<prime.length-1; i++) {
if(!prime[i]) {
for(int j=i*i; j<=prime.length-1; j+=i) {
prime[j] = true;
}
}
}
int start = 0;
int end = 0;
String numRange = scan.nextLine();
String[] strArr = numRange.split(" ");
start = Integer.parseInt(strArr[0]);
end = Integer.parseInt(strArr[1]);
for(int i=start; i<=end; i++) {
if(!prime[i]) System.out.println(i);
}
}
}
※ 성공 분석
- 효과적으로 소수를 찾으려면 '에라토스테네스의 체'를 반드시 이해해야한다.
이것은 "소수인 수의 배수를 모두 제외하면 남은 것은 소수가 된다."는 개념이다.
위 이미지와 같은 방식을 코드로 구현하면 시간복잡도는 O(n^2)와 가깝다.
두 코드의 큰 차이는 실패코드는 숫자마다 계속 소수판독을 해줘야 하지만 성공코드는 전체를 한 번만 소수판독을 해주면 된다.
자세한 내용을 알고 싶다면 아래 위키백과 한 번 정독을 추천한다.
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서
ko.wikipedia.org
728x90
'자기계발 > 백준 문제 풀이' 카테고리의 다른 글
7568 자바 ] 덩치(풀이) (0) | 2022.09.01 |
---|---|
1009 자바 ] 분산처리(풀이) (0) | 2022.09.01 |
10757 자바 ] 큰 수 A+B(풀이) (0) | 2022.09.01 |
11720 자바 ] 숫자의 합 (풀이) (0) | 2022.09.01 |
2108 자바 ] 통계학(풀이) (0) | 2022.09.01 |