개발하는 사막여우

세그먼트 트리란 ? 배열 또는 리스트와 같은 데이터 구조를 이용하여 구간에 대한 질의를 효율적으로 처리하는 자료구조 주어진 구간에 대한 쿼리 연산을 빠르게 수행할 수 있도록 도와줌. 주로 구간 합, 최솟값 최댓값 등. 트리 구조를 사용하여 데이터를 분할하고 각 분할된 영역에 대한 요약정보를 저장. 이를 통해 트정 구간에 대한 연산을 빠르게 수행할 수 있음 트리를 구축하는 초기 비용이 크지만, 이 후 구간 질의에 대해 빠르게 답을 제공할 수 있음으로 효율적 세그먼트 트리 구조 시간복잡도 트리를 구축: O(N) 합, 곱 계산(쿼리 연산): O(logN) 값의 갱신(업데이트 연산): O(logN) => N은 배열의 크기이며, 구간에 대한 연산을 처리하는 경우 logN만큼의 시간이 들기 때문에 세그먼트 트리의 ..

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 = ..