Traveling Programmer

🤔 A -> B 관계가 성립하는 DAG에서 어떻게 정렬을 할 수 있을까?DAG부터 알아보자.DAG란 Directed Acyclic Graph의 약자로 방향성이 있으며 사이클이 없는 그래프를 말한다. 무슨 말일까?위의 그림을 보면 더욱 명확하게 이해가 될 것이다. A -> C, A -> B의 간선이 존재하지만 C -> A, B -> A로 갈 수 있는 방법이 없기 때문에 사이클이 존재하지는 않는다. 우리는 이러한 관계에서 어떠한 규칙에 따라 이를 정렬하고 싶은 경우를 알아볼 것이다.📖 위상정렬이란? 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 여기서 하나의 용어를 알아야 한다. 바로 진입 차수(Indegree)이다.예를 들면 2의 경우 자신에게 들어오는..

문제https://www.acmicpc.net/problem/20543풀이(1시간)import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parse..

문제https://www.acmicpc.net/problem/13424풀이(14분)import java.util.*;import java.lang.*;import java.io.*;public class Main { // N개의 방 1~N번 번호 붙어있음 // N개의 방은 M개의 통로로 연결 ( 양방향 통로이며 자연수 길이 가짐 ) // K명이 참여 // N개의 방중에서 한개씩 각각 위치해있음(K 방 개수가 200이하인지 생각하자. // 학생들이 위치한 점을 List로 저장해두고, 그 점에서 도달하는 점들의 거리를 누적합하여 해결하자. static int T, N, M; static int[][] floyd; static final int MAX = 1_000..

문제https://www.acmicpc.net/problem/5052풀이(19분)import java.util.*;import java.lang.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); loop1: while(t-- > 0){ int n = Integer.parseInt(br.readLine()..

🤔 문제의식평소 코딩 테스트 연습을 하다 보면 split을 사용하는 경우가 많다.하지만 때때로 원하는 반환값이 아닌 예상외의 값이 나왔고, 이를 처리하기 위해 각종 분기문을 추가한 적이 있다.왜 그런 것인지 정리하고, 깔끔하게 코드를 작성하고 싶었다.📖 String.split()public String[] split(String regex) { return split(regex, 0, false);}private String[] split(String regex, int limit, boolean withDelimiters) { /* fastpath if the regex is a * (1) one-char String and this character is not one of th..

문제https://www.acmicpc.net/problem/15886풀이(20분)import java.util.*;import java.lang.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); String map = br.readLine(); // "EW"를 기준으로 나누고, 빈 문자열도 유지 String[..

문제https://www.acmicpc.net/problem/3165풀이(45분)import java.io.*;import java.util.*;public class Main { private static final char FIVE = '5'; private static StringBuilder number; private static int targetCount; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Strin..

문제https://www.acmicpc.net/problem/15993풀이(12분)import java.io.*;import java.util.*;public class Main { static final int MOD = 1_000_000_009; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int T = Integer.parseInt(br.readLine()); int[] nums = new int[T]; ..

문제https://www.acmicpc.net/problem/1749풀이(21분)import java.io.*;import java.util.*;public class Main { static int N, M; static int[][] arr; static int[][] prefixSum; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); ..

문제https://www.acmicpc.net/problem/1275풀이(20분)import java.io.*;import java.util.*;public class Main { static int N, Q, squareNum; static long[] segment; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); N = Integer.pa..