백준298 [백준] 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. [백준] 2075번 : N번째 큰 수 – JAVA [자바] https://www.acmicpc.net/problem/2075 문제 해결 방법이 문제를 해결하는 가장 직관적인 방법은 N×N개의 숫자를 정렬한 후 N번째 큰 값을 찾는 것이다. 하지만 이는 O(N² log N²) = O(N² log N)의 시간 복잡도를 가지므로, N = 1500인 경우 비효율적일 수 있다. 이를 해결하기 위해 우선순위 큐(PriorityQueue)를 활용하여 메모리를 절약하고 실행 속도를 개선할 수 있다. 최적화 방법 (최소 힙 사용)1. 최소 힙(PriorityQueue)을 사용하여 최대 N개의 숫자만 저장2. 처음 N개의 숫자는 힙에 삽입3. N+1번째 숫자부터는 힙의 최솟값(peek)보다 크면 교체4. N×N개의 숫자를 모두 처리한 후, 힙의 최솟값이 N번째 큰 수 이 방.. 2025. 3. 18. [백준] 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 2 3 4 5 ··· 75 다음 반응형
