반응형 에라토스테네스의체4 백준 6588번 골드바흐의 추측 - C++ 풀이 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 에라토스테네스의 체를 이용하여 백만 이하의 모든 소수를 구한다. n이하의 모든 소수 i에 대해 n-i가 소수인지 판별하면 된다. 이때 i를 오름차순으로 순회하고, 답이 나올 경우 순회를 종료시키면 b-a가 가장 큰 답을 구할 수 있다. 백만 이하의 소수 개수는 약 8만 개이므로, 이 풀이의 시간 복잡도는 O(80,000*T)이다. 이때 T(테스트 케이스 수)가 10^5이므로 시간 초과가 날 것 같았는데 시간 초과가 나지 않았다. 이에 관련된 질문과 답을 아래 게시글에서 발견하였다. 글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요? 댓글을 작성하려면 로그인해야 합니.. 2022. 9. 20. 백준 1963번 소수 경로 - C++ 풀이 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다. #include #include using namespace std; const int INF = 987654.. 2022. 8. 20. 백준 2581번 소수 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. 1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다. 에라토스테네스의 체를 이용하면 O(NloglongN)에 1 이상 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. N이 최대 10,000이기 때문에 굳이 에라토스테네스의 체를 사용하지 않아도 1~(i-1)까지로 전부 나눠봐서 소수인지 판별하는 O(N^2)을 알고리즘을 사용해도 시간 내에 통과가 가능하다. 2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다. M부터 N까지 단순 순회하면서 소수들만 골라 더하고, 처음으로 나오.. 2022. 2. 10. 백준 1644번 소수의 연속합 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 일단 소수들을 구해야 한다. N=4,000,000이므로 4,000,000 이하인 소수 목록을 다 구한다. 에라토스테네스의 체를 사용하면 O(NloglogN)에 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. 그리고 나서 소수들만 추려 배열을 만든다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 연속하는 모든 구간을 탐색하는 것은 불가능하다. 소수 개수(M)가 약 280,000개 이므로 O(M^2)의 시간 복잡도로는 .. 2022. 2. 3. 이전 1 다음 반응형
