반응형 Prime6 BOJ 1644 : 소수의 연속합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1644 N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다. 따라서, 소수의 판단은 에라토스테네스의 체를 이용한다. int N; int prime[4000000 + 50000]; int primeSet[4000000 + 50000]; int pcnt; void eratos() { prime[1] = 1; for (int i = 2; i * i 2021. 4. 2. BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19. BOJ 6588 : 골드바흐의 추측 알고리즘 문제 전체 링크 www.acmicpc.net/problem/6588 어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다. 매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에, 주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다. 즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다. 그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다. 주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로, 가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다. primeNumber[st]가 소수이고 .. 2021. 3. 16. 에라토스테네스의 체 - 소수 판단 C, C++ 전체 링크 어떤 수 하나를 소수 판단할 경우는 링크에서 for문을 돌면서 판단할 수 있다. 하지만 매번 숫자를 소수 판단하면 비용이 많이 들기 때문에, memoization 기법으로, 특정 숫자가 소수인지 미리 체크해두면 편하다. 이때, 사용하는 알고리즘이 에라토스테네스의 체 이다. 배열 prime[]은 소수인 경우 0, 소수가 아닌 경우 1로 표시하자. 이제 1 ~ 50의 경우 소수를 판단하는 원리를 알아보자. 먼저, 1은 소수가 아니므로 지운다. prime[1] = 1 이제부터 에라토스테네스의 체가 시작된다. 에라토스테네스의 체에 걸려있지 않다면, 소수다. 현재 2는 에라토스테네스의 체에 걸려있지 않으므로, 소수이다. 그리고 2 부터 2칸씩 모두 소수가 아니므로 지운다. prime[2 *.. 2021. 3. 16. 소수 판단 함수 C, C++ 전체 링크 참고 - 에라토스테네스의 체 - 소수 판단 어떤 수가 소수인지 판단하는 방법은 나눠떨어지는 수가 있는지 직접 나눠보면 된다. 예를 들어 13을 소수인지 아닌지 판단해보자. 1로 나누는 것은 의미가 없으므로, 2부터 나눠보자. 13 / 2 는 나눠떨어지지 않는다. 13 / 3 는 나눠떨어지지 않는다. 13 / 4 는 나눠떨어지지 않는다. ... 13 / 12 는 나눠떨어지지 않는다. 따라서 13은 소수이다. 하지만 이 과정을 다 해볼 필요는 없다. 2 부터 12까지가 아니라 √13까지만 나눠보면 된다. 만약 √13보다 작은 수에서 나눠 떨어지는 수가 있다면 √13보다 큰 수에서도 나눠떨어지기 때문이다. c/c++에서 math 함수를 이용하면 루트를 계산할 수 있지만, 라이브러리를 사.. 2021. 3. 14. 해시 테이블 성능 비교 및 소수 찾기 (BOJ 1620) 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 BOJ 1620의 MAX_TABLE을 바꿔가면서 성능을 비교해보자. BOJ 1620의 N = 100,000이다. 순서대로 MAX_TABLE = 100 (작은 값이고 소수가 아님) MAX_TABLE = 107 (작은 값이고 소수) MAX_TABLE = 100,000 (N과 비슷한 값이지만 소수가 아님) MAX_TABLE = 100,003 (N과 비슷한 값이지만 소수) MAX_TABLE = 200,000 (N의 2배, 소수가 아님) MAX_TABLE = 200,009 .. 2021. 2. 16. 이전 1 다음 반응형
