Algorithm
[백준] 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..
최단 거리
최단 거리
2022.06.27BFS와 다익스트라 알고리즘을 통해 그래프에서 특정 노드까지의 최단 거리를 구할 수 있다. BFS를 통해 계산하는 경우는 한 번 이동할 때 카운트를 하나씩 늘려가면 되고.. 해당 개념을 사용해 문제도 좀 풀어봐서 익숙하다. 이 때, 간선의 가중치는 1만 가능하다. 다익스트라 알고리즘은 간선의 가중치가 0이상 일 때 사용할 수 있다. 다익스트라 알고리즘에 대해 자세히 알아보자. Dijkstra 그래프 자료구조와 시작 노드가 주어지고, 시작점에서 모든 노드까지의 최단 거리를 출력하는 알고리즘이다. dist[] : 시작점에서 특정 정점까지의 최단 거리를 담는 배열이다. (다익스트라의 결과를 담는 배열) D (v, d) : 시작점에서 v까지 가는데 d만큼이 사용된다. 1. 시작점을 S라고 하자. dist[i]에..
위상정렬
위상정렬
2022.06.24Topological Sort 그래프 자료구조에 대해 정렬을 수행할 때 위상정렬을 사용한다. 위상정렬은 DAG 그래프에 대해서만 수행 할 수 있다. (사이클이 없고 방향성이 있는 그래프) 위상정렬을 통해 DAG에서 간선의 방향성에 따라 정점을 위상에 맞춰 정렬해보자. N에서 K로 가는 간선이 있다면 N은 K보다 먼저 나타나야 한다. 위의 조건을 충족하면서 정점들을 나열하는 것을 위상정렬이라고 한다. 위의 조건 때문에, 사이클이 있는 그래프에 대해서는 위상정렬을 수행할 수 없다. 이제 위상정렬의 과정에 대해 알아보자. 제일 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다. 위의 그래프에서 정점 1 9 7은 들어오는 간선이 없기 때문에 정렬을 수행한 결과 중 앞에 위치한다. (1 9 7 간의 순서는 ..
[백준] 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..