개발하는 사막여우

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int N,M,..

https://www.acmicpc.net/problem/1268 1268번: 임시 반장 정하기 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. www.acmicpc.net 소스코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new String..

https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 소스코드 package Baekjoon.DP; import java.io.*; import java.util.*; class P7570 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb ..

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 소스코드 package Baekjoon.DP; import java.io.*; import java.util.*; class P2631 { public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb =..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 소스코드 import java.util.*; import java.io.*; class Main { static long[] tree,lazy,arr; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new I..

BFS란 루트 노드 (혹은 시작 노드)에서 시작하여 인접한 노드를 먼저 방문하는 알고리즘입니다. 즉 DFS와 같이 깊이를 먼저 탐색하는 것이 아니라 자신 주변을 넓게 탐색하여 너비 우선 탐색이라고 불립니다. BFS로 최단경로를 찾을 수 있는 이유는 한 정점에서 연결되는 모든 길을 "한번씩" 탐색하기 때문입니다. 특정 노드와 연결된 노드 사이의 길이는 1이기 때문에 같은 방식으로 모든 노드 사이의 거리를 구할 수 있기 때문입니다. 하지만 가중치가 있는 그래프의 경우 BFS를 사용할 수 없습니다 ! BFS의 특징 그래프 탐색 시, 어떤 노드를 방문했는지 여부를 반드시 검사해야 합니다. 검사하지 않았을 경우, 무한루프에 빠질 수 있습니다. BFS 알고리즘은 일반적으로 선입선출(FIFO)의 특징을 가지는 큐 자..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 소스코드 import java.io.*; import java.util.*; class Main { static long[] arr; static int a,b,c; static final int MOD = 1000000007; public static class SegmentTree { long[] tree; int treeSize;..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 소스코드 import java.util.*; import java.io.*; class Main { static long[] arr; static int a,b; static long c; public static class SegmentTree { long[] tree; int treeSize; public SegmentTree(int ..

https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 소스코드 package Baekjoon.브루트포스; import java.util.*; import java.io.*; class P20529 { static int bt; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int T = ..

우선순위 큐란 ? - 일반적인 큐의 구조 FIFO(First In First Out)의 구조를 가지지만, 데이터가 들어온 순서대로 빠져나가는 것이 아니라, 우선순위를 결정하고, 우선순위에 따라 데이터가 출력되는 구조입니다 . - 내부가 힙의 구조로 되어있기 때문에 O(nlogn)의 시간복잡도를 가지게 됩니다. - 배열에 값을 추가하면서 따로 정렬하지 않더라도 자동으로 정렬되는 것이 장점입니다. 우선순위 큐 선언 import java.util.PriorityQueue; PriorityQueue hq = new PriorityQueue(); 우선순위에 따른 최대, 최소 힙 - 최소힙: 최솟값이 우선순위인 큐 import java.util.PriorityQueue; PriorityQueue hq = new P..