분류 전체보기403 [백준] 11725번 : 트리의 부모 찾기 – JAVA [자바] https://www.acmicpc.net/problem/11725 문제 해결 방법이 문제는 루트 없는 트리에서 각 노드의 부모를 찾는 문제이다. BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)을 활용하여 해결할 수 있다.1. 그래프 구성입력으로 주어진 트리의 연결 정보를 이용하여 인접 리스트를 만든다.각 노드는 서로 연결된 상태이며, 양방향 간선으로 주어진다.2. BFS를 이용한 부모 노드 찾기BFS(너비 우선 탐색) 방법을 사용한다.루트 노드(1번 노드)부터 탐색을 시작하며, 자식 노드들의 부모를 기록한다.방문한 노드는 다시 방문하지 않도록 한다.3. 결과 출력2번 노드부터 N번 노드까지의 부모를 순서대로 출력한다. 코드 import java.io.*;import java.util.*.. 2025. 3. 25. [백준] 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. 이전 1 2 3 4 5 6 ··· 101 다음 반응형
