골랜디 Virtual #3
알고리즘 : 2/8
SQL : 3/3
중첩 집합 모델
https://www.acmicpc.net/problem/19641
틀렸습니다. 업솔빙 했습니다.
트리에서 먼저 방문할 수록 가장 작은 숫자를 부여하고,
마지막에 방문할수록 가장 큰 숫자를 부여하면, 문제에서 주어진대로 범위가 주어집니다.
public class Main { static int N, A, B, H, W; static int answer = 0; static int[] left, right; static int timer = 1; static ArrayList<Integer>[] adj; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); adj = new ArrayList[N+1]; for(int i=1; i<=N; i++) { adj[i] = new ArrayList<>(); } for(int i=0; i<N; i++) { st = new StringTokenizer(br.readLine()); int node = Integer.parseInt(st.nextToken()); while(st.hasMoreTokens()) { int next = Integer.parseInt(st.nextToken()); if(next == -1) break; adj[node].add(next); } } st = new StringTokenizer(br.readLine()); int root = Integer.parseInt(st.nextToken()); for(int i=1; i<=N; i++) { Collections.sort(adj[i]); } left = new int[N+1]; right = new int[N+1]; //DFS 수행 : 루트노트부터 시작, 부모는 0으로 지정 dfs(root, 0); for(int i=1; i<=N; i++) { System.out.println(i + " " + left[i] + " "+ right[i]); } } //DFS 함수 : 현재 노드 u, 부모 노드 parent static void dfs(int u, int parent) { left[u] = timer++; for(int v : adj[u]) { if(v == parent) continue; dfs(v, u); } right[u] = timer++; } }
팀배분
https://www.acmicpc.net/problem/1953
업솔빙했습니다.
처음에 문제를 보고 유니온 파인드를 활용해서
- 적의 적은 나의 동지다.
- 동지의 적은 나의 적이다.
이렇게 접근해야하는 것인가 생각했지만, 이분그래프 특성을 이용한다면 훨씬 간단했습니다.
문제의 조건으로, 애초에 반드시 분할가능하다는 입력만 주어진다는 조건이 주어집니다.
이분그래프이므로, 내가 만약 청색팀이라면, 내가 싫어하는 팀은 반드시 백팀입니다.
이를 활용해서 BFS로 만날때마다 바로바로 반대의 색깔로 칠해주면 됩니다.
public class Main { static int N, A, B, H, W; static int answer = 0; static ArrayList<Integer>[] disLikeList; static int[] team; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); disLikeList = new ArrayList[N+1]; for(int i=1; i<=N; i++) { disLikeList[i] = new ArrayList<>(); } for(int i=1; i<=N; i++) { st = new StringTokenizer(br.readLine()); int count = Integer.parseInt(st.nextToken()); for(int j=0; j<count; j++) { int disLikedPerson = Integer.parseInt(st.nextToken()); disLikeList[i].add(disLikedPerson); disLikeList[disLikedPerson].add(i); } } team = new int[N+1]; for(int i=1; i<=N; i++) { team[i] = -1; } for(int i=1; i<=N; i++) { if(team[i] == -1) { bfs(i); } } //결과를 저장할 리스트 ArrayList<Integer> blueTeam = new ArrayList<>(); ArrayList<Integer> whiteTeam = new ArrayList<>(); for(int i=1; i<=N; i++) { if(team[i] == 0) { blueTeam.add(i); } else { whiteTeam.add(i); } } Collections.sort(blueTeam); Collections.sort(whiteTeam); System.out.println(blueTeam.size()); for(int v : blueTeam) { System.out.print(v+" "); } System.out.println(); System.out.println(whiteTeam.size()); for(int v : whiteTeam) { System.out.print(v+" "); } } //BFS를 통해 이분 그래프 색칠 static void bfs(int start) { Queue<Integer> q = new LinkedList<>(); q.add(start); team[start] = 0; while(!q.isEmpty()) { int here = q.poll(); for(int neighbor:disLikeList[here]) { if(team[neighbor] == -1) { team[neighbor] = 1 - team[here]; q.add(neighbor); } } } } }
아기 홍윤
https://www.acmicpc.net/problem/24023
업솔빙했습니다만, 시간초과로 해결하지 못했습니다.
슬라이딩 윈도우로 접근했습니다. 또한 BitWise 연산은 반드시 증가할 수 밖에 없다는점을 유의합니다.
- 해당 범위의 BitWise 결과가
특정 수 K 라면, 해당 범위가 정답이고,
K보다 크다면, Left로 K보다 작아질떄까지 계속 LEft를 이동시켜주고,
K보다 작다면, 계속해서 right를 증가시키면서 처리하면 됩니다.
public class Main { static int N, A, B, H, W, K; static int answer = 0; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); arr = new int[N]; st = new StringTokenizer(br.readLine()); for(int i=0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } int left = 0; int bitWiseRet = 0; for(int right = 0; right < N; right++) { bitWiseRet |= arr[right]; while(left <= right && bitWiseRet > K) { bitWiseRet = 0; left++; for(int i=left; i<=right; i++) { bitWiseRet |= arr[i]; } } if(bitWiseRet == K) { System.out.println((left+1)+" "+(right+1)); return ; } } System.out.println(-1); } }
게임 오브 데쓰 (Easy)
https://www.acmicpc.net/problem/32654
업솔빙했습니다.
DP[k][i] : K번쨰 턴에 i번쨰 참가자가 지목될 수 있는지 여부 (T/F)를 저장합니다.
해당 부분을 정의하고, 상향식으로 하나하나 채워나가면 됩니다.
만약 K = 10 ~ 99 까지 검사하면서 상윤이가 한번이라도 T인경우가 존재한다면, 그 K값을 반환하면 됩니다.
public class Main { static int N, A, B, H, W, K; static int answer = -1; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int[] L = new int[N + 1]; int[] R = new int[N + 1]; for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); L[i] = Integer.parseInt(st.nextToken()); R[i] = Integer.parseInt(st.nextToken()); } int maxK = 99; // dp[k][i] : k번 전달 후 i번 참가자가 차례를 받을 수 있는지 여부 boolean[][] dp = new boolean[maxK + 1][N + 1]; dp[0][1] = true; for (int step = 0; step < maxK; step++) { for (int i = 1; i <= N; i++) { if (dp[step][i]) { dp[step + 1][L[i]] = true; dp[step + 1][R[i]] = true; } } } int answer = -1; for (int k = 10; k <= 99; k++) { if (!dp[k][1]) { answer = k; break; } } System.out.println(answer); } }
1211. Queries Quality and Percentage
https://leetcode.com/problems/queries-quality-and-percentage/?envType=study-plan-v2&envId=top-sql-50
테이블을 GROUP BY 한 이후의 테이블을 예측하고, 각 집계함수를 적용하면 됩니다.
/* Write your PL/SQL query statement below */ SELECT Q.QUERY_NAME, ROUND(SUM(Q.RATING/Q.POSITION) / COUNT(Q.QUERY_NAME), 2) AS QUALITY, ROUND(SUM(CASE WHEN RATING < 3 THEN 1 ELSE 0 END) / COUNT(Q.QUERY_NAME) * 100, 2) AS POOR_QUERY_PERCENTAGE FROM QUERIES Q GROUP BY Q.QUERY_NAME
1633. Percentage of Users Attended a Contest
SELECT R.CONTEST_ID, ROUND(COUNT(U.USER_ID) / (SELECT COUNT(*) FROM USERS) * 100, 2) AS PERCENTAGE FROM REGISTER R INNER JOIN USERS U ON R.USER_ID = U.USER_ID GROUP BY R.CONTEST_ID ORDER BY PERCENTAGE DESC, CONTEST_ID ASC
2356. Number of Unique Subjects Taught by Each Teacher
/* Write your PL/SQL query statement below */ SELECT T.TEACHER_ID, COUNT(DISTINCT T.SUBJECT_ID) AS CNT FROM TEACHER T GROUP BY T.TEACHER_ID
등수 찾기
https://www.acmicpc.net/problem/17616
업솔빙했습니다.
문제가 어려운점은, 등수를 표현하기 위해 어떻게 해야하지라는 생각부터가 시작입니다.
나의 최대 등수는(낮을수록 좋은 것입니다.) -- > (나보다 확실히 점수가 높은 학생들의 수) + 1
나의 최소 등수(가장 최악의 경우) -> 전체학생수 (N) - (나보다 점수가 낮은 학생 수) 입니다.
나보다 점수가 높은 학생들이 많다면, 나의 등수가 자연스레 떨어집니다.
나보다 점수가 낮은 학생들이 많다면, 나의 등수가 자연스레 올라갑니다.
위와 같이 정리가 되었다면, 아래와 같이 접근합니다.
1. graph에 나보다 더 못한 학생들에게 간선으로 연결합니다.
2. reverseGraph에 나보다 더 잘한 학생들에게 간선으로 연결합니다.
중요점은, 1->3->4 일떄의 연관관계입니다. 1이 3보다 더 잘했다면, 자연스레 1이 4보다 더 잘했다는 의미입니다.
package Main; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Main { static int N, A, B, H, W, K, D, C, S, T, M, L, X; static int answer = 0; static int[] arr; static List<Integer>[] graph; static List<Integer>[] reverseGraph; static boolean[] visited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); X = Integer.parseInt(st.nextToken()) - 1; //그래프 초기화 graph = new ArrayList[N]; reverseGraph = new ArrayList[N]; for(int i=0; i<N; i++) { graph[i] = new ArrayList<>(); reverseGraph[i] = new ArrayList<>(); } for(int i=0; i<M; i++) { st = new StringTokenizer(br.readLine()); A = Integer.parseInt(st.nextToken()) - 1; B = Integer.parseInt(st.nextToken()) - 1; graph[A].add(B); reverseGraph[B].add(A); } visited = new boolean[N]; int worseThanX = findWorseDfs(X); Arrays.fill(visited, false); int betterThanX = findBetterDfs(X); int minRank =betterThanX + 1; int maxRank = N - worseThanX; System.out.println(minRank+" "+maxRank); } static int findWorseDfs(int start) { int ret = 0; for(int i=0; i<graph[start].size(); i++) { int next = graph[start].get(i); if(visited[next] == false) { visited[next] = true; ret += 1 + findWorseDfs(next); } } return ret; } static int findBetterDfs(int start) { int ret = 0; for(int i=0; i<reverseGraph[start].size(); i++) { int next = reverseGraph[start].get(i); if(visited[next] == false) { visited[next] = true; ret += 1 + findBetterDfs(next); } } return ret; } }
문제의 핵심은 , 그래프의 구성된 싸이클 없는 간선의 개수를 구하라는 것과 같은데, 문제가 해당 본질을 이해하지 못하도록 하기에 어렵습니다.
회전 초밥
https://www.acmicpc.net/problem/15961
전형적인 슬라이딩 윈도우 문제입니다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { static int N, A, B, H, W, K, D, C; static int answer = 0; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); D = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); arr = new int[2*N]; for(int i=0; i<N; i++) { st = new StringTokenizer(br.readLine()); arr[i] = Integer.parseInt(st.nextToken()); } for(int i=N; i<2*N; i++) { arr[i] = arr[i-N]; } //처음 K-1개 먼저 먹음 HashMap<Integer, Integer> hashmap = new HashMap<>(); for(int i=0; i<K; i++) { hashmap.put(arr[i], hashmap.getOrDefault(arr[i], 0) + 1); if(hashmap.containsKey(C) == false) { answer = Math.max(answer, hashmap.size() + 1); }else { answer = Math.max(answer, hashmap.size()); } } for(int right=K; right<2*N; right++) { int num = hashmap.get(arr[right - K]); if(num <= 1) { hashmap.remove(arr[right - K]); }else if(num >= 2) { hashmap.put(arr[right - K], num - 1); } hashmap.put(arr[right], hashmap.getOrDefault(arr[right], 0) + 1); if(hashmap.containsKey(C) == false) { answer = Math.max(answer, hashmap.size() + 1); }else { answer = Math.max(answer, hashmap.size()); } } System.out.println(answer); } }
사회적 거리 두기
https://www.acmicpc.net/problem/20917
매개변수 탐색을 활용합니다.
문제에서 가장 핵심은, 의자 간의 거리를 미리 정해두고 그 거리가 가능한지를 확인하는 것 입니다.
특이점은 항상 의자간의 거리를 구할때 맨 앞 의자에서부터 시작해도 됩니다. ( 이 부분이 헷갈릴 수 있으나, 반드시 맨 앞에서부터 앉아야 그것이 최선 값입니다. )
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.StringTokenizer; public class Main { static int N, A, B, H, W, K, D, C, S, T; static int answer = 0; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); T = Integer.parseInt(st.nextToken()); while(T -- > 0) { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); S = Integer.parseInt(st.nextToken()); arr = new int[N]; st = new StringTokenizer(br.readLine()); for(int i=0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr); System.out.println(optimize(0, N)); } } static int optimize(int s, int e) { int left = -1; int right = 1000000001; while(left + 1 < right) { int mid = (left + right) / 2; if(decision(mid) == true) { left = mid; }else { right = mid; } } return right - 1; } static boolean decision(int dist) { int seatCnt = 1; int seatPos = arr[0]; for(int i=1; i<N; i++) { if(arr[i] - seatPos >= dist) { seatCnt += 1; seatPos = arr[i]; } } return seatCnt >= S; } }
휴게소 세우기
https://www.acmicpc.net/problem/1477
업솔빙했습니다. 매개변수 탐색을 활용하는 것까지는 알았으나, 구현에 어려움이 있었습니다.
이 문제 같은 경우 휴게소 간 길이를 매개변수로 두고, 해당 길이로 휴게소를 배치했을때 딱 M개가 되는지가 쟁점입니다.
하지만, decision 결정함수를 구현하면서, arr[i+1] - arr[i] - 1 에서 -1 을 하는거라든지와 같이, 혹은 휴게소의 시작점과 끝점은 냅두는 것. 그리고 이분탐색에서 제가 구현한 방식은 (lo, hi)이기에 [lo + 1, hi - 1]의 범위를 가진다는 점들에 어려움을 겪어서 구현하지 못했습니다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.StringTokenizer; public class Main { static int N, A, B, H, W, K, D, C, S, T, M, L; static int answer = 0; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); L = Integer.parseInt(st.nextToken()); arr = new int[N + 2]; arr[0] = 0; st = new StringTokenizer(br.readLine()); for(int i=1; i<=N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } arr[N+1] = L; Arrays.sort(arr); System.out.println(optimize()); } static int optimize() { int left = 0; int right = L; //휴게소 간 길이가 매개변수가 됩니다. //해당 매개변수로 휴게소를 지을 수 있다면, 더 줄여봅니다. while(left + 1 < right) { int mid = (left + right) / 2; if(decision(mid) == true) { left = mid; }else { right = mid; } } return right; } static boolean decision(int dist) { int cnt = 0; for(int i=0; i<N+1; i++) { cnt += (arr[i+1] - arr[i] - 1) / dist; } return cnt > M; } }
'알고리즘 > 랜덤디펜스' 카테고리의 다른 글
[백준][랜덤디펜스] 골랜디 Virtual #3 (0) | 2025.04.15 |
---|---|
[백준][랜덤디펜스] 골랜디 Virtual #2 (0) | 2025.04.13 |
[백준][랜덤디펜스] 골랜디 Virtual #2 (0) | 2025.04.12 |