에라토스테네스의 체7 [백준] 1644번 - 소수의 연속합 [Java] https://www.acmicpc.net/problem/1644 1. 아이디어 에라토스테네스의 체를 이용해서 소수를 구하고 투 포인터 알고리즘으로 연속합을 구하는 방식을 활용하면 해결할 수 있다.2. 문제풀이 에라토스테네스의 체를 이용해서 소수 리스트를 먼저 구했다.이후 투 포인터 알고리즘을 활용해서 소수의 연속합을 구하는데 포인터는 둘다 앞쪽에 위치시킨채 소수의 연속합이 N보다 작으면 오른쪽 포인터를 한칸 오른쪽으로, N보다 크면 왼쪽 포인터를 한칸 오른쪽으로 이동시키는 방식으로 구현했다.N이 1일 경우 예외처리를 해줘야 했는데 그냥 main 메서드에서 바로 종료하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { .. 2025. 1. 7. [백준] 2960번 - 에라토스테네스의 체 [Java] https://www.acmicpc.net/problem/2960 1. 아이디어 에라토스테네스의 체의 구현 원리와 유사한 문제로 2중 for문을 통해 에라토스테네스의 체를 구현하는 로직을 약간 수정하면 해결할 수 있다.2. 문제풀이 방문체크를 통해 중복 제거를 방지하고 order 변수로 K번째 여부를 파악하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 1. 7. [백준] 1963번 - 소수 경로 [Java] https://www.acmicpc.net/problem/1963 1. 아이디어 에라토스테네스의 체를 이용한 소수 판정과 BFS 알고리즘을 조합해서 소수 경로의 길이를 구할 수 있다.2. 문제풀이 먼저 에라토스테네스의 체로 1000부터 9999 사이의 소수를 구해서 HashSet에 저장했다.이후 BFS 알고리즘에서 4자리 소수의 각 자릿수를 바꿔보며 소수이면 Queue에 넣는 방식으로 구현했다.몫과 나머지 연산을 응용해서 특정 자릿수 변경을 해주면 간단하게 구현할 수 있다.소수 경로는 BFS 알고리즘의 최단 경로 구하기와 동일하다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[].. 2025. 1. 7. [백준] 15965번 - K번째 소수 [Java] https://www.acmicpc.net/problem/15965 1. 아이디어 에라토스테네스의 체로 소수 리스트를 미리 구하고 인덱스로 찾는 방식으로 구현했다.자연수가 최대 500,000으로 주어졌는데, 50만번째 소수가 1000만 이하 범위에 있는 점으로 좀 더 간편하게 구현했다.2. 문제풀이 에라토스테네스의 체로 소수 여부를 먼저 판정을 하고 해당 결과로 소수 리스트를 구했다.K번째 소수는 소수 리스트에서 K-1 인덱스에 위치한다는 점을 이용하면 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 12. 4. [백준] 2581번 - 소수 [Java] https://www.acmicpc.net/problem/2581 1. 아이디어 소수 판정에 유용한 에라토스테네스의 체를 활용하면 간단하게 해결할 수 있다.2. 문제풀이 N의 범위가 10,000 이하의 자연수로 주어져 있으므로 10,000 이하의 소수를 판정하는 boolean 타입 배열을 구하고 이를 대조하는 방식으로 구현했다.M부터 N까지 반복문을 순회하며 합과 최솟값을 갱신하면 간단하게 구현할 수 있다.최솟값은 한번만 갱신해도 되지만 가독성을 위해 그냥 반복문 안에 넣었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 12. 3. [백준] 1929번 - 소수 구하기 [Java] https://www.acmicpc.net/problem/1929 1. 아이디어 소수 판정에 유용한 에라토스테네스의 체를 활용하면 간단하게 해결할 수 있다.2. 문제풀이 N의 범위가 1,000,000 이하의 자연수로 주어져 있으므로 1,000,000 이하의 소수를 판정하는 boolean 타입 배열을 구하고 이를 대조하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2024. 12. 3. [백준] 1978번 - 소수 찾기 [Java] https://www.acmicpc.net/problem/1978 1. 아이디어 소수 판정에 유용한 에라토스테네스의 체를 활용하면 간단하게 해결할 수 있다.2. 문제풀이 N의 범위가 1,000 이하의 자연수로 주어져 있으므로 1,000 이하의 소수를 판정하는 boolean 타입 배열을 구하고 이를 대조하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St.. 2024. 12. 3. 이전 1 다음
