에라토스테네스의체3 [백준] 1990번 : 소수인팰린드롬 – JAVA [자바] https://www.acmicpc.net/problem/1990 문제 해결 방법이 문제는 소수 판별 및 팰린드롬 검사를 활용한 수 필터링 문제이다. 다음과 같은 방식으로 해결할 수 있다.1. B까지의 소수를 구한다. 에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 구한다. BitSet을 사용하여 불필요한 메모리 사용을 줄이고 빠르게 소수를 판별한다. 여기서 BitSet이란 비트 단위로 값을 저장하는 자바의 자료구조이다. 즉, 1개의 비트(0 또는 1)만 사용하여 데이터를 관리할 수 있다. Boolean 값(true/false)을 비트 단위로 저장하므로, 메모리를 크게 절약할 수 있다. 자바에서 boolean []을 사용하면, 각 boolean 값이 1 byte (8 bits)를 차지한다. 하.. 2025. 3. 19. [백준] 11502번 : 세 개의 소수 문제 – JAVA [자바] https://www.acmicpc.net/problem/11502 문제 해결 방법이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용한다. 1. 소수 목록 생성- 7부터 999까지의 홀수 중 소수들을 미리 구해놓는다.- 에라토스테네스의 체를 사용하여 빠르게 소수를 판별한다. 에라토스테네스의 체의 대한 자세한 정보는 여기서 확인할 수 있다. 2. 세 개의 소수로 표현 가능한지 확인- 세 개의 소수를 더해서 K가 되는 조합을 찾는다.- 오름차순 정렬된 결과를 출력한다.- 여러 답이 있을 경우, 발견한 첫 번째 조합을 출력한다.- 불가능한 경우 0을 출력한다. 이제 이를 바탕으로 코드 구현을 진행한다. 코드 import java.io.*;import java.util.*;public class .. 2025. 3. 18. [백준] 1124번 : 언더프라임 – JAVA [자바] https://www.acmicpc.net/problem/1124 문제 해결 방법이 문제는 소수 판별 및 소인수분해를 활용한 수 카운팅 문제이다. 다음과 같은 방식으로 해결할 수 있다. 1. B까지의 소수를 구한다.- 에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 구한다. 에라토스테네스의 체의 대한 자세한 정보는 여기서 확인할 수 있다. 2. 각 숫자의 소인수 개수를 구한다.- B 이하의 모든 수에 대해 소인수분해를 수행하여 소수 개수를 센다. 3. 소인수 개수가 소수인지 확인하여 카운트한다.- A부터 B까지의 숫자 중에서 소인수 개수가 소수인 경우를 센다. 이 방법을 사용하면 O(N log log N + N log N)의 시간 복잡도로 문제를 해결할 수 있다. 코드 import jav.. 2025. 3. 17. 이전 1 다음 반응형
