* 최대 시행 횟수가 1,000,000개가 넘어가는 프로그램에 시간복잡도가 n^2인 로직을 넣으면
BOJ에서는 바로 시간초과를 낸다. 따라서 더 효율적인 로직으로 소수를 구해야 하는데, 이때
사용될 수학 원리가 바로 '에라토스테네스의 체'이다.
* 에라토스테네스의 체란, 어떤 수 n보다 작은 소수들을 모두 구할 때, 2 <= m < n인 수에 대해
m=2부터 시작하여, n보다 작은 모든 수들을 나눴을 때 자기 자신이 아닌 수로 나눠지면 지우고, 다음 수 m=3으로 나눴을 때도 자기 자신이 아닌 수로 나눠지면 지우는 방식으로 m=n-1까지 돌렸을 때 남는 수가 소수라고 생각할 수 있다.
** 설명이 이상하지만, 원리는 같다.
* C++로 구현했는데, 에라토스테네스의 체를 이용한 내 생각대로 구현해봐도 시간초과가 나서 새로운 개념을 배웠다.
바로 std::ios_base::sync_with_stdio(false)와 std::cout.tie(NULL) 코드이다.
std::ios_base::sync_with_stdio(false)를 이용하면 c의 stdio의 버퍼와 연결해제되어 iostream에서 c의 버퍼는 더이상 이용할 수 없게 되지만 수행속도는 빨라진다는 장점이 있다.
std::cout.tie(NULL)는 기존에 한 쌍으로 묶여있던 cin과 cout버퍼를 분리해주는 것이다. 수없이 많은 횟수의 입출력을 반복해야 하는 알고리즘문제의 특성상 필수적으로 버퍼를 분리해주는 것이 좋다.
** 시간초과 해결에 대한 아이디어를 구하던 중 신박한 해결책을 알게 되었다.
바로 소수를 구하는 로직에서, 소수를 판정할 때 나눠주는 수의 범위를 전체의 sqrt를 해줘도 상관없다는 것이다.
왜 그럴까?
전체 범위를 sqrt한 값이 해당로직의 가운데 경계가 되기 때문이다.
N = 16인 경우를 생각해보면, sqrt(N) = 4를 중심으로 이전과 이후의 실행은 똑같은 알고리즘이 된다.
따라서 i <= sqrt(16) = 4 인 경우만 실행해 줘도 된다는 의미이다.
제곱근을 이용하여 범위를 지정해 줄때는 부등식에 등호조건이 무조건 들어가야 한다. 그래야 전체 범위를
포괄해주기 때문이다. 등호조건이 없다면 경계가 되는 부분이 반복문에 포함되지 않는다는 말과 같다.
#include <iostream>
using namespace std;
// 소수 구하기
// 더 적은 시간의 알고리즘
int main() {
ios_base::sync_with_stdio(false); cout.tie(NULL);
int M, N; cin >> M >> N;
int* a = new int[N]();
for (int i = 1; i <= N; i++) {
a[i - 1] = i;
}
a[0] = 0;
// i의 범위 설정할 때 sqrt를 썼으면 등호를 무조건 붙여줘야 함
for (int i = 2; i*i <= N; i++) {
for (int j = M-1; j < N; j++) {
if (a[j] == 0) {
continue;
}
if (a[j] % i == 0 && a[j] != i) {
a[j] = 0;
}
}
}
for (int i = M-1; i < N; i++) {
if (a[i] != 0) { cout << a[i] << '\n'; }
}
delete[] a;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[Baekjoon] 1436_영화감독 숌 (0) | 2022.04.10 |
---|---|
[Baekjoon] github repository 생성 (0) | 2022.04.08 |
백준 단계별 풀이 (0) | 2022.03.13 |
백준 단계별 풀이 (0) | 2022.03.13 |