전체 글411 [백준] 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. [백준] 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. [백준] 1145번 : 적어도 대부분의 배수 – JAVA [자바] https://www.acmicpc.net/problem/1145 문제 해결 방법 이 문제는 최소 공배수(LCM, Least Common Multiple) 개념을 활용하여 해결할 수 있다. 다섯 개의 수 중에서 적어도 세 개로 나누어지는 가장 작은 자연수를 찾아야 하므로, 세 개의 숫자를 조합하여 최소 공배수를 구하고, 그중 최솟값을 선택하면 된다. 문제 해결 과정 1. 다섯 개의 자연수를 입력받는다. 2. 다섯 개 중 세 개를 선택하는 모든 조합을 찾는다. 3. 선택한 세 개의 수의 최소 공배수(LCM)를 구한다. 4. 모든 조합의 LCM 중에서 최솟값을 출력한다. 최대 공약수(GCD, Greatest Common Divisor)는 두 수의 공통된 약수 중 가장 큰 값을 의미하며, 유클리드 호제법을.. 2025. 3. 14. [백준] 12852번 : 1로 만들기 2 – JAVA [자바] https://www.acmicpc.net/problem/12852 문제 해결 방법 이 문제는 DP 방법을 이용하여 해결할 수 있다. 1. dp[i]를 i를 1로 만들기 위한 최소 연산 횟수 라고 정의한다. 2. 초기값을 설정한다: dp[1] = 0 (1은 연산 없이 1이므로 연산 횟수가 0) 3. dp[i] 값을 dp[i-1], dp[i/2], dp[i/3] 중 최소값 +1로 설정한다. 4. dp[n]을 통해 최소 연산 횟수를 구한 후, 역추적(backtracking)을 이용하여 경로를 출력한다. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOEx.. 2025. 3. 14. [백준] 1439번 : 뒤집기 – JAVA [자바] https://www.acmicpc.net/problem/1439 문제 해결 방법 이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다. 1. 0과 1이 각각 몇 번 그룹으로 나뉘는지 계산한다. 예를 들어 0001100의 경우, 000 / 11 / 00으로 0 그룹 2개, 1 그룹 1개가 된다. 11001100110011000001의 경우, 11 / 00 / 11 / 00 / 11 / 00 / 11 / 00000 / 1로 0 그룹 4개, 1 그룹 4개가 된다. 2. 0과 1의 그룹 수 중 작은 값을 선택하면 최소 뒤집기 횟수가 된다. 예를 들어 0001100의 경우 0 그룹 2개, 1 그룹 1개이므로 최소 1번 뒤집으면 해결 가능하다. 110011001100110000.. 2025. 3. 13. 이전 1 2 3 4 5 6 ··· 52 다음 반응형
