Traveling Programmer

진행하는 과정에서 생길 수 있는 부분에 대해서는 Q.라고 적어두고 하단부에 모두 설명할 테니 참고하자. 개념주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태가 바로 세그먼트 트리이다.더 큰 범위는 '인덱스 트리'라고 불린다.1차원 배열에서의 구간합 저장 배열을 이용하는 것보다 복잡한 과정을 거치지만, 업데이트가 발생하는 경우 효율적인 성능을 발휘한다.Q. 데이터 업데이트가 왜 빠른가요?Q. 구간 곱, 최대 최소 탐색에는 어떻게 활용하나요?세그먼트 트리 수행 과정우리는 {3, 1, 4, 1, 5, 9, 2, 6} 배열의 구간합을 예시로 세그먼트 트리를 이해해 볼 것이다.우리가 구간합을 구하고자 하는 배열을 생각해보자. 총 8개의 숫자로 구성된 배열이다. 이를 이진트..

문제https://www.acmicpc.net/problem/1019풀이(30분)import java.io.*;public class Main { static long[] numCount = new long[10]; // 0부터 9까지 각 숫자의 등장 횟수를 저장할 배열 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // 입력값 N int start = 1; // 시작 숫자 int ..

문제https://www.acmicpc.net/problem/16565풀이(50분)import java.io.*;public class Main { static final int MOD = 10007; static int[][] comb = new int[53][53]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int ans = 0; // 조합 초기화 for ..

문제https://www.acmicpc.net/problem/13334풀이(40분)import java.io.*;import java.util.*;public class Main { static final List intervals = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); for (int i = 0; i pq = new PriorityQueue(); //..

문제https://www.acmicpc.net/problem/14725풀이(30분)import java.io.*;import java.util.*;public class Main { // 어차피 끝까지 내려가는 것은 보장되어있다. // 그럼 중요한 것은 깊이에 따른 사전순 배열이다. // 길이는 중요하지않고 사전순 배열이기만 하면 된다. // 또한 이걸 출력하는 것이 중요하다. static final String FLOOR_SEPARATOR = "--"; // 구분자 public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputSt..

문제https://www.acmicpc.net/problem/1613풀이(45분)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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextT..

문제https://www.acmicpc.net/problem/1516풀이(30분)import java.io.*;import java.util.*;public class Main { // 배열에는 완공되어야 하는 개수 -> 이게 0이 된 것을 큐?에 넣는다. // 큐는 시간이 늘어남에 따라 완공할 수 있는 건물을 추적한다. // 건물 완성 배열과완공 건물갯수도 추적해야할듯? // 맵에는 >로 어떤 건물을 완공하면 지을 수 있는 건물들을 추적한다. static int n; static int[][] building; static boolean[] completed; static HashMap> list = new HashMap(); static Priority..

문제https://www.acmicpc.net/problem/17472풀이(40분)import java.io.*;import java.util.*;public class Main { static final int INF = Integer.MAX_VALUE; // 무한대 값 상수로 선언 static int n, m, answer; static int[] parent; static int[][] map; static int[] dx = {0, 0, -1, 1}; // 상하좌우 static int[] dy = {-1, 1, 0, 0}; static int[][] lengthMap; static PriorityQueue pq = new PriorityQueue(); ..

문제https://www.acmicpc.net/problem/1774풀이(25분)import java.io.*;import java.util.*;public class Main { // 이미 교감하는 존재가 있다! // 우주신들과 교감의 통로가 길어지면 힘듬 // 거리는 2차원 좌표계상의 거리와 같다 // 새로 만들어야 할 정신적인 통로의 길이들의 합이 최소가 되게 // 그럼 일단 연결된 애들은 부모를 같게 한다. // 나머지 모든 점들에 대해 거리를 구하고, 노드에 넣자! static int n; static PriorityQueue pq = new PriorityQueue(); static int[] parent; static int answer;..

문제https://www.acmicpc.net/problem/1744풀이(15분)import java.io.*;import java.util.*;public class Main { // 양수의 경우 내림차순으로 해서 곱해서 더하자 // 음수의 경우 오름차순으로 해서 곱해서 더하자 // 0은 버리자 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int answer = 0; ..