Stargazer

접근: 어떤 자연수가 주어지면 그것보다는 작은 소수의 합의 갯수를 구하는 것이므로, n보다 작은 소수의 배열을 구하고, 그에 맞는 구간 합을 구하면 된다. 전략: 소수를 구하는 것은 에라스토테네스의 체를 이용하여 구하면 되고, 구간합은 투 포인터(two pointers)를 이용하여 구하면 된다. 코드: #include #include #include using namespace std; vector sosu; //n이하 소수 배열 bool so[4000001]; //소수 판별 배열 int n; int sum = 0; int s = 0, e = 0; int res = 0; int main(){ cin >> n; for(int i=2;i= sosu.size()) break; sum += sosu[e++]; ..

특징: Worst case에 대해서는 $O(n^2)$ 시간이지만, Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다. 전략: Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법 *단계: 1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔) 3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다. * 분할 정복 알고리즘 수도 코드: solve(I) n=size(I) if(n