1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include #include #include #include using namespace std; const int MAX_N = 10000001; int minfac[MAX_N]; int testCase, n, lo, hi; void era() { for(int i = 2; i testCase; for(int i = 0; i >n>>lo>>..

소수(prime number) 소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다. 소수의 반대: 합성수(composite number): 세 개 이상의 양의 약수를 갖는 자연수 가장 단순한 소수판별: 2 부터 n -1 까지 모든 수를 순회, n의 약수가 있는지 확인 (합성수의 성질에 따라 sqrt(n)이하 까지 순회하도록 최적화 가능) (비트 수에 따라 수행시간이 증가 => 비트 수가 하나 증가 => 수행시간 두배 => 지수시간) (1, 2, 3 제외 한 모든 소수는 6k +- 1 형태임을 이용할 수 도 있다.) (2 를 제외하면 모든 짝수는 소수가 아니다.) 1 2 3 4 5 6 7 8 9 10 bool isPrime(int n) { if(n

1. 기하 이 문제는 위와 같이 블록 껍질이 주어졌을 때 겹치는 다각형의 최대 수직 거리를 구하는 문제이다. 기하적으로 푸는 법은 다음과 같다. - 교차되는 직선들의 교차점을 포함하고 두 블록 껍질의 교집합인 점들을 포함하는 블록껍질을 구한다. - 구한 교집합 블록껍질의 꼭지점들을 X좌표에서 수직을 그어 최대인 수직 거리를 구한다. (블록 껍질에서의 최대 수직 거리는 항상 꼭지점에서 그은 수직선이다. 기울기가 꼭짓점에서 바뀌기 때문이다.) 먼저 블록껍질의 점 하나를 다른 블록껍질의 선분들에 대응하면서 포함되는지 확인 해야 한다. 교집합이 될 수 있는 점의 범위를 최소화 하여 포함되는지 확인하자. A와 B의 X값의 최대 최소를 비교하여 X값의 범위를 A와 B의 Y값의 최대 최소를 비교하여 Y값의 범위를 줄..

1. 수치 해석 직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘 이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야로, 공학, 과학, 금융과학 등 다양한 범위에 널리 사용 2. 이분법(bisection method) [lo, hi] 내에서 어떤 함수 f(x)의 값이 0이 되는 지점을 수치적으로 찾아내는 기법. 답이 여러 개 있는 함수라도 연속이기만 하다면 이분법을 사용해 근을 찾을 수 있음. 이분법을 사용하기 위해서는 우선 함수의 그래프 상에서 x축 윗부분에 위치한 점 하나와 아랫부분에 위치한 점 하나르 찾아야한다. (lo, hi) 그래프가 연속인 경우 중간값 정리에 의해 두 점 사이에서 그래프가 x축을 만나는 지점이 반드시 존재한다. lo와 hi의 중간점에서 f(x)를 검사하고 만..

1. 최적 문제 n개의 강의 중에서 k개이상의 강의만 남겨놓고 철회할 때 최소 누적 등수를 구하는 문제이다. 이것은 k개 까지 하나 하나 철회해보면서 누적등수를 계산하고 그 중에서 최소값을 구하는 최적화 문제이다. 이 문제를 결정문제로 변형해보자 2. 결정 문제 isOkay(r) = r의 누적등수가 주어졌을 때 이것보다 작은값이 있는가? 위와 같은 식을 토대로 함수를 작성해 보았다. isOkay는 k개 까지 모든 경우를 세서 주어진 누적등수보다 작은 값이 나오면 true 작은 값이 나오지 않을 경우 false를 반환한다. 하지만 이 함수는 최악의 경우 2^1000 개를 카운트하므로 당연히 제출한 코드는 시간 초과를 내뿜었다. 이전 꺼랑 비교해서 더 큰값이 나올 경우 가지치기하려는 생각도 해봤지만 답을 구..

1. 결정 문제 이 문제를 결정문제로 해석한뒤 이진법으로 풀어보자 D에 k번째 표지판이 있는지? 이것을 이진법으로 0 , 8030,000 까지 탐색하면 답이 나올 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include #include int T, N, K; int L[5000], M[5000], G[5000]; bool search(int D) { int sign = 0; for(int i = 0; i = L[i] - M[i]) sign += 1 + (std::min(D,L[i]) - L[i] + M[..