Algorithm/Baekjoon
[백준] 1931 회의실 배정 - Java
[백준] 1931 회의실 배정 - Java
2022.06.27그리디 문제에는 정렬이 따라오는 경우가 많다. 정렬의 기준을 뭐로 설정할지가 매우 중요하다. 이 부분에 대해 고민해보자. 이 문제의 경우는 끝나는 시간을 오름차순으로 정렬하고, 같다면 시작 시간을 오름차순으로 정렬해야 한다. import java.util.*; import java.io.*; import java.math.*; 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()); Time[] arr = new Ti..
[백준] 1753 최단경로 - Java
[백준] 1753 최단경로 - Java
2022.06.27그래프를 입력받고 다익스트라 알고리즘을 돌려서 풀 수 있는 문제이다. 다익스트라 알고리즘을 알고 구현할 수 있으면 풀 수 있는 문제라서.. 더 설명할 건 없다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N, M, start; static int[] dist; static ArrayList[] edge; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Str..
[백준] 2252 줄 세우기 - Java
[백준] 2252 줄 세우기 - Java
2022.06.24주어지는 입력을 DAG로 표현하고, 위상정렬로 정렬해서 풀 수 있다. import java.util.*; import java.io.*; import java.math.*; public class Main { static ArrayList[] adj; static int[] indegree; static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); Deque dq = new LinkedList(..
[백준] 3961 터치스크린 키보드 - Java
[백준] 3961 터치스크린 키보드 - Java
2022.06.23char타입의 이차원 배열을 사용해 문자 간의 거리를 계산할 때 사용해줬고, 문자열과 문자열의 오차를 다루는 클래스를 생성해 정렬 시 사용해줬다. import java.util.*; import java.io.*; import java.math.*; 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()); char[][] dictionary = new char[3][10]; String str1 = "qwertyuio..
[백준] 6166 문자열 암호화 - Java
[백준] 6166 문자열 암호화 - Java
2022.06.22암호화 과정은 복호화 과정을 반대로 수행하면 된다. char타입 배열을 선언하고, 입력받은 숫자 N을 기준으로 N칸씩 넘어가며 배열을 채워주자. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true){ int N = Integer.parseInt(br.readLine()); if(N == 0){ break; } String str = br.readLine(); st..
[백준] 1068 트리 - Java
[백준] 1068 트리 - Java
2022.06.22리스트를 사용해 트리를 구현하고, 지울 요소를 입력받은 후 해당하는 요소를 리스트에서 모두 제거해 준 다음 dfs 돌려서 리프 노드의 수를 탐색해줬다. 리스트에서 indexOf(i) 메서드를 통해 위치를 리스트에 포함된 i의 위치를 얻고, 얻은 위치를 바탕으로 요소를 제거할 수 있었다.. 트리를 여러 개의 subtree로 분할한 후 각각의 subtree에 대해 또 subtree로 분할하고.. 이 작업을 자식이 없는 노드가 될 떄 까지 반복한 후 개수를 갱신해 주는 방식으로 풀어도 괜찮을 것 같다. (재귀 느낌으로?) import java.util.*; import java.io.*; import java.math.*; public class Main { static int N; static ArrayLi..
[백준] 3649 로봇 프로젝트 - Java
[백준] 3649 로봇 프로젝트 - Java
2022.06.12문제 자체는 정렬하고 투포인터 방식으로 하나는 배열의 시작부터, 다른 하나는 배열의 끝부분부터 차례대로 확인하면 풀 수 있는 문제인데, EOF처리가 까다롭다. EOF처리를 가장 간단하게 할 수 있는 방법 하나를 소개하려 한다. EOF처리를 해 주지 않은 상태로 코드를 집어넣으면 채점기에서 EOF에러를 뱉는다. 자바에서 에러를 처리할 때 try catch문법을 사용하는데, EOF역시 에러 중 하나이기에 try catch문에서 잡힌다. 대부분은 while(br.readLine() != null) 이렇게 처리할텐데, 지금처럼 입력이 한 줄 단위로 주어지지 않을 경우에는 try catch로 처리하는 방법도 시도해 보자. import java.io.*; import java.util.*; public class ..
[백준] 5567 결혼식 - Java
[백준] 5567 결혼식 - Java
2022.05.28bfs / dfs를 돌릴 필요 없이 리스트로 그래프를 표현하는것만으로 풀 수 있다. 상근이의 학번은 1이니, 리스트1에 해당하는 원소들을 추가해 주고 (친구 탐색) 친구의 친구를 구하기 위해 추가된 원소들에 대해 다시 한 번 탐색을 수행하자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int target1; static int target2; static int[] parent; static ArrayList[] list; static boolean[] visit; static int[] dist; static StringBuilder sb = new StringBuilder(); ..
[백준] 2644 촌수계산 - Java
[백준] 2644 촌수계산 - Java
2022.05.28주어진 입력을 리스트 형태의 그래프로 저장하고, 그래프에 대해 bfs를 돌리면서 촌수를 갱신하자. 이 때 dist배열을 사용해 촌수를 갱신한다. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int target1; static int target2; static int[] parent; static ArrayList[] list; static boolean[] visit; static int[] dist; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOExcepti..
[백준] 11725 트리의 부모 찾기 - Java
[백준] 11725 트리의 부모 찾기 - Java
2022.05.28입력을 그래프로 처리하고 나면, 리스트에 포함된 첫 번째 원소가 해당 노드의 부모가 된다. 트리는 모든 노드가 연결되어있음이 보장되므로, 노드 1부터 시작해 bfs를 돌며 모든 노드의 부모를 찾자. import java.util.*; import java.io.*; public class Main { static int N; static int[] parent; static ArrayList[] list; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..
[백준] 11403 경로 찾기 - Java
[백준] 11403 경로 찾기 - Java
2022.05.27행렬 형태로 주어진 그래프를 이용해 탐색을 수행해야 한다. 행에 대해서 bfs를 돌린 후 해당하는 행이 접근할 수 있는 열을 기록하고 출력한다. 주어진 조건에서 i,i에 해당하는 좌표는 무조건 0으로 주어진다고 했으니, visit를 체크할 때 주의하자. import java.util.*; import java.io.*; public class Main { static int N; static int[][] map; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..
[백준] 3184 양 - Java
[백준] 3184 양 - Java
2022.05.27영역에 속한 양과 늑대의 수를 비교해 연산을 수행해야 한다. 영역을 구할 때는 dfs를 돌려서 구할 수 있다. 매 시행마다 영역 안에 있는 양의 수와 늑대의 수를 초기화 해야 됨을 잊지 말자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static char map[][]; static boolean[][] visit; static int cnt; static int[][] dir = {{1,0}, {-1,0}, {0,-1}, {0,1}}; static int wolf_cnt = 0; static int sheep_cnt = 0; static int wolf_ans = 0; static int s..