본문 바로가기

에라토스테네스의 체16

[자바] 백준 1990 - 소수인팰린드롬 (java) 문제 : boj1990 필요 알고리즘 개념 소수 판정, 에라토스테네스의 체 팰린드롬도 판정해야하지만, 그보다 먼저 소수 판정을 할 수 있어야 한다. 에라토스테네스의 체를 알고 있어야 1억 이하의 소수를 효율적으로 구할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. b 이하의 소수를 모두 구한다. 에라토스테네스의 체를 사용해 구해주면 된다. 이 때 sqrt(b) 까지만 확인해주면 된다. (에라토스테네스의 체 혹.. 2022. 11. 10.
[자바] 백준 1456 - 거의 소수 (java) 문제 : boj1456 필요 알고리즘 개념 소수 판정, 에라토스테네스의 체 범위 내의 모든 소수를 찾아야 하므로 소수 판정, 더 나아가 에라토스테네스의 체를 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 소수의 N제곱(N>=2) 꼴일 때를 찾아줘야 한다. 이 때 오른쪽 범위 B가 10^14이고 N>=2 이므로 최대 10^7까지의(sqrt(B) 까지 알아야 한다) 모든 소수를 찾아야 함을 알 수 있다... 2022. 8. 12.
[자바] 백준 22943 - 수 (java) 문제 : boj22943 필요 알고리즘 개념 브루트포스 가능한 모든 경우에 대해 완전탐색을 통해 경우의 수를 찾아줄꺼다. 에라토스테네스의 체 소수 판정 알고리즘이다. 한 개의 수가 소수인지 판정할때는 안쓰인다. 이 문제에서는 특정 범위 이내의 모든 소수를 찾아두고 풀이를 진행할 것이므로 에라토스테네스의 체를 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 이 문제를 풀기위해 알아야 하는 것들을 생각해보자. 1... 2022. 7. 28.
[자바] 백준 9842 - Prime 문제 : boj9842 에라토스테네스의 체로 10000번째 소수를 구할 만큼 큰 수까지의 모든 소수를 구한 후 입력받은 n번째 소수를 출력해주면 된다. 이 때, 10000번째 소수는 104,729이다. 어떻게 알았냐면 대충 15만으로 두고 돌려보니 104729까지였다.(!) 코드 : github(java) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { private static final int LIMIT = 104729; ArrayList pn = new ArrayList(); private void initPn() { boolean[] isPn =.. 2022. 4. 22.
백준 1644 자바 - 소수의 연속합 (boj 1644 java) 문제 : boj1644 소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ). 투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어.. 2022. 4. 5.
백준 18384 자바 - PRIM (BOJ 18384 JAVA) 문제 : boj18384 이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다. 1. 1000000보다 처음으로 큰 소수까지의 모든 소수 2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기 '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다. '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 .. 2022. 3. 22.