소수 판정16 [자바] 백준 16563 - 어려운 소인수분해 (java) 목차 문제 : boj16563 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본.. 2024. 2. 23. [자바] 백준 3142 - 즐거운 삶을 위한 노력 (java) 목차 문제 : boj3142 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 완전제곱수인지 우선 생각해보자. 내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다. 예를들어서 예제 입력 2를.. 2024. 2. 23. [자바] 백준 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. [자바] 백준 2986 - 파스칼 (java) 문제 : boj2986 필요 알고리즘 개념 소수 판정 소수 판정 시 소수인지 알고 싶은 값 N에 대해 sqrt(N) 까지만 살펴보면 된다는 점을 알아야 풀 수 있다. 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 글에서 해당 개념을 익힐 수 있다. 수학, 정수론 기본적인 수학 지식이 있어야 풀 수 있다. 정확힌 나머지 연산에 대한 개념과 소수(prime number)가 무엇인지, 약수가 무엇인지 정도만 알면 된다. 나머지 연산 : 코드에서는 일반적으로 '%'로 표현된다. A%B는 A를 B로 나누고 남은 나머지를 뜻한다. A%B==0 이라면 B가 A의 약수임을 뜻한다. 소수(prime number) : 2이상의 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 예를들어 2,3,.. 2022. 8. 7. [자바] 백준 22943 - 수 (java) 문제 : boj22943 필요 알고리즘 개념 브루트포스 가능한 모든 경우에 대해 완전탐색을 통해 경우의 수를 찾아줄꺼다. 에라토스테네스의 체 소수 판정 알고리즘이다. 한 개의 수가 소수인지 판정할때는 안쓰인다. 이 문제에서는 특정 범위 이내의 모든 소수를 찾아두고 풀이를 진행할 것이므로 에라토스테네스의 체를 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 이 문제를 풀기위해 알아야 하는 것들을 생각해보자. 1... 2022. 7. 28. [자바] 백준 2153 - 소수 단어 (boj 2153) 문제 : boj2153 1. 문자를 문제에서 제시된 방법대로 합계를 구할 수 있어야 한다. -> 문자의 각 character인 c를 확인하면서 아래처럼 구하자. - 'a'~'z'인 경우 : sum += 1+c-'a'; - 'A'~'Z'인 경우 : sum += 27+c-'A'; 2. '1'에서 구한 sum이 소수인지 소수판정을 해야 한다. -> 이 경우 2부터 sqrt(sum) 까지의 정수로 직접 나눠보고, 이 중 하나라도 sum을 나누어떨어지게(나머지가 0) 하는 값이 있다면 소수가 아니다. sqrt(sum) 까지 확인하는 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에 적어두었다(링크). 코드 : github import java.io.BufferedReader;.. 2022. 7. 5. [자바] 백준 1241 - 머리 톡톡 (boj java) 문제 : boj1241 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유(글 링크) 이 글을 이해했다면 쉽게 풀 수 있다. N개를 입력받으면서 HashMap 등으로 각 숫자의 존재 여부 및 몇 개 존재하는지 저장해둔다. 이후 N개를 순회하면서 각각을 A라고 하면, 1부터 sqrt(A) 사이에 존재하는 A의 약수가 B라 하자. 그럼 HashMap에서 B의 개수를 더해주고, A/B도 약수일 것이므로 그것도 HashMap에서 찾아 더해주면 된다. 이 때 주의점은 sqrt(A)로 A가 나누어 떨어질 경우 (즉, (int)sqrt(A) * (int)sqrt(A) == A 인 경우), 두 번 더해지게 되므로 한 번은 빼줘야 한다. 그럼 시간복잡도는 N명 중 가장 큰 숫자가 K라 할 때, O(N.. 2022. 4. 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. 이전 1 2 다음
