알고리즘/백준
-
[백준]10216. Count Circle Groups (Java)알고리즘/백준 2021. 9. 3. 15:03
💡 문제 분석/** * 1. 적군의 좌표를 가지고 그래프를 만들어서, 모든 적군을 순회하면서 그래프 탐색이 몇번 일어나는지 카운트하는 방법 * 2. 유니온 - 파인드 자료구조를 만들어서, 루트의 개수를 세는 방법 */ ⌨️ 코드JAVAimport java.io.*; import java.util.*; public class Q10216 { static int N; static List[] adj; static Enemy[] enemies; static boolean[] check; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); // tc번 반복 while(tc-- > 0) ..
-
[백준]10026. 적록색약 (Java)알고리즘/백준 2021. 9. 3. 15:03
💡 문제 분석/** * 적록 색약인 사람이 봤을 때는 R과 G를 같은 값으로 생각해야 함. * 모든 칸을 순회하면서 그래프 탐색으로 컴포넌트 개수를 찾고, * G와 R을 같은 값으로 통일 시킨 뒤 한번 더 그래프 탐색을 하면 될 것같음. */ ⌨️ 코드JAVAimport java.io.*; import java.util.*; public class Q10026 { static final int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; static int N, ret1, ret2; static char[][] board; static boolean[][] visited; public static void main(String[] args) { Scanner sc = new..
-
[백준]9252. LCS2 (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * 앞서 만들었던 LCS 메소드를 이용해서 실제 최장공통부분수열을 구합니다. * 1. A[a]와 B[b]가 같다면 선택합니다 * 2. 다음 위치로 넘어갈 때 최장 공통 부분 수열의 길이가 긴 쪽을 선택해서 만듭니다 */ ⌨️ 코드 JAVA import java.io.*; import java.util.*; public class Q9252 { static char[] A, B; static int[][] cache; public static void main(String[] args){ Scanner sc = new Scanner(System.in); A = sc.next().toCharArray(); B = sc.next().toCharArray(); cache = new int[..
-
[백준]9251. LCS (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * A와 B의 위치를 하나씩 옮겨가면서 전부 비교해본다 * 서로 값이 같았다면 공통 부분이기 때문에 + 1 * 같지 않다면 다음 위치로 넘어가자 */ ⌨️ 코드 JAVA import java.io.*; import java.util.*; public class Q9251 { static char[] A, B; static int[][] cache; public static void main(String[] args){ Scanner sc = new Scanner(System.in); A = sc.next().toCharArray(); B = sc.next().toCharArray(); cache = new int[A.length + 1][B.length + 1]; for(int i ..
-
[백준]9084. 동전 (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * dp[n][m] = coin[n]원 이상의 동전으로 m원을 만들기 */ ⌨️ 코드 JAVA import java.io.*; import java.util.*; public class Q9084 { static int N, M; static int[] coin; static int[][] cache; public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T-- > 0) { N = sc.nextInt(); coin = new int[N]; for(int i = 0; i < N; i++) coin[i] = sc.nextInt(); M = sc.nextI..
-
[백준]9019. DSLR (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * 각각의 상태에서 D, S, L, R 네 가지의 연산을 하는 것으로 BFS를 실행하자 * 명령어를 출력해야 하기 때문에, 각각의 단계에서 골랐던 명령어를 저장해 놓아야 겠다. */ ⌨️ 코드 JAVA import java.util.*; public class Q9019 { static char[] ops = {'D', 'S', 'L', 'R'}; static int[][] choice; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T-- > 0) { int A = sc.nextInt..
-
[백준]7662. 이중 우선순위 큐 (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * 하나의 우선순위큐에서 최대값과, 최솟값을 뽑아내야 하므로 트리맵을 사용하는 것이 좋을 듯 * 중복이 허용되므로 = 형태로저장하는게 좋겠다. * */ ⌨️ 코드 JAVA import java.io.*; import java.util.*; public class Q7662 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T-- > 0) { int k = sc.nextInt(); TreeMap ts = new TreeMap(); for(int iter = 0; iter < k; iter++) { char c = sc.next().charAt(0..
-
[백준]7511. 소셜 네트워킹 어플리케이션 (Java)알고리즘/백준 2021. 8. 30. 21:46
💡 문제 분석 /** * 10만명이라서 플로이드는 안될 것 같고, * 유니온 파인드로 친구관계를 서치하면 되겠다 */ ⌨️ 코드 JAVA import java.io.*; import java.util.*; public class Q7511 { static int N, K, M; static int[] parent; static StringTokenizer st; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = stoi(br.readLine()); for(int t = 1; t