에라토스테네스의 체20 [자바] 백준 27650 - 마법박스 (java) 목차문제 : boj27650 필요 알고리즘매개 변수 탐색 (이분 탐색), 에라토스테네스의 체문제에서 제시된 것의 규칙을 찾아, 20번 내에 물어볼 수 있는 방법을 찾아야 한다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음엔 무지성으로 단순히 최대 500만개짜리 배열 만들어두고, 2부터 시작하면서 물어보고 1이라고 하면 2의 배수 전부 체크하는 식으로 생각했었다. 문제는 인터랙티브 문제라 틀렸습니다라고 안떴다는 점이.. 2024. 5. 17. [자바] 백준 16563 - 어려운 소인수분해 (java) 목차 문제 : boj16563 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본.. 2024. 2. 23. [자바] 백준 3142 - 즐거운 삶을 위한 노력 (java) 목차 문제 : boj3142 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 완전제곱수인지 우선 생각해보자. 내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다. 예를들어서 예제 입력 2를.. 2024. 2. 23. [자바] 백준 16400 - 소수 화폐 (java) 목차 문제 : boj16400 필요 알고리즘 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 순서대로 생각해보자. 1. N이하의 화폐를 모두 알아야 한다. -> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의.. 2023. 12. 15. [자바] 백준 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. 이전 1 2 다음
