BOJ23 [BOJ] [JAVA] 31423번 신촌 통폐합 계획 31423번: 신촌 통폐합 계획 첫 번째 줄에 대학교의 개수 $N$이 주어진다. $(2 \leq N \leq 500 \, 000)$ 다음 $N$개의 줄의 $i$번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 $s_i$가 주어진다. 주어지는 대학교 www.acmicpc.net Union Find에서 Path Compression과 방식이 유사한 것 같아 작성한다. (아닐수도,,,) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static String[] str; public.. 2024. 2. 21. [BOJ] [JAVA] 2252번 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 문제다. 사이클이 없는 방향 그래프의 모든 노드들을 순서에 맞춰 정렬하는 알고리즘이다. 노드에 들어오는 간선의 개수인 진입차수가 0인 노드들은 수행할 수 있는 상태의 노드들이므로 큐에 넣는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; .. 2024. 2. 20. [BOJ] [JAVA] 1238번 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 그래프의 정점과 간선이 주어지고 각 정점에서 특정 정점(파티)까지 갔다가 되돌아는 최단거리 중 최댓값을 구하는 문제다. 다익스트라 알고리즘을 활용해서 해결할 수 있었다. 다익스트라는 임의의 시작점에서부터 다른 노드로 가는 최단거리를 구할 수 있는 알고리즘이다. 다이내믹 프로그래밍과 유사하다고 느꼈다. dp의 일종인가? 그래프를 두 가지로 동시에 입력받았다. 하나는 입력 그대로의 그래프 (파티에서 각자의 집으로 돌아갈 때 다익스트라를.. 2024. 2. 16. [BOJ] [JAVA] 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 그래프의 시작 지점에서 각 정점으로 갈 수 있는 최단 거리를 계산하는 문제다. 다익스트라 알고리즘을 활용해서 해결할 수 있다. 처음에는 인접 행렬을 이용해보려 했지만, V 2024. 2. 15. 이전 1 2 3 4 ··· 6 다음
