Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 코멘토 #코멘토실무PT #실무PT후기 #실무강의 #리액트강의 #웹프로그래밍 #react #웹개발실무
- 프론트엔드
- invalid_grant
- 유효시간 설정 url
- Dev-Matching
- 스프링부트
- 자바스크립트
- 파일 url
- Deep Dive
- 프로그래머스
- 우아한 테크코스
- AWS
- concurrency limit
- NestJS
- api 비동기처리
- compateto
- oauth
- 딥다이브
- 모던 자바스크립트
- api 요청 수 제한
- 우아한테크코스
- this
- 프리코스
- 타입스크립트
- TypeORM
- 검색
- 음악 url 파일 다운로드
- 프론트엔드 과제
- bucket4j
- redis
Archives
- Today
- Total
개발 알다가도 모르겠네요
삼성 SDS 대학생 알고리즘 특강 8일차 - 그래프 본문
728x90
3176: 도로 네트워크
import java.util.*;
import java.io.*;
class Main {
static int N, D, depth[], dp[][], min[][], max[][];
static List<int[]> adj[];
static void bfs(int root) {
Queue<Integer> q = new LinkedList<>();
q.add(root);
depth[root] = 1;
while(!q.isEmpty()) {
int curr = q.poll();
for(int i = 0; i < adj[curr].size(); i++) {
int[] next = adj[curr].get(i);
int nv = next[0];
int w = next[1];
if(depth[nv] > 0) continue;
dp[0][nv] = curr;
max[0][nv] = min[0][nv] = w;
depth[nv] = depth[curr] + 1;
q.add(nv);
}
}
}
static int[] lca(int u, int v) {
int min_ = Integer.MAX_VALUE, max_ = Integer.MIN_VALUE;
if(depth[u] > depth[v]) {
int temp = u;
u = v;
v = temp;
}
int diff = depth[v] - depth[u];
for(int i = 0; i <= D; i++) {
if(((1 << i) & diff) > 0) {
min_ = Math.min(min_, min[i][v]);
max_ = Math.max(max_, max[i][v]);
v = dp[i][v];
}
}
if(u != v) {
for(int i = D-1; i >= 0; i--) {
if(dp[i][u] != dp[i][v]) {
min_ = Math.min(min_, Math.min(min[i][u], min[i][v]));
max_ = Math.max(max_, Math.max(max[i][u], max[i][v]));
u = dp[i][u];
v = dp[i][v];
}
}
min_ = Math.min(min_, Math.min(min[0][u], min[0][v]));
max_ = Math.max(max_, Math.max(max[0][u], max[0][v]));
}
return new int[] {min_, max_};
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
for(; (1 << D) < N; D++);
depth = new int[N+1];
dp = new int[D][N+1];
min = new int[D][N+1];
max = new int[D][N+1];
adj = new ArrayList[N+1];
for(int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
}
for(int i = 1; i < N; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
adj[u].add(new int[] {v, w});
adj[v].add(new int[] {u, w});
}
//tree 생성
bfs(1);
//sparse table 생성
for(int j = 1; j < D; j++) {
for(int i = 1; i <= N; i++) {
dp[j][i] = dp[j-1][dp[j-1][i]];
min[j][i] = Math.min(min[j-1][i], min[j-1][dp[j-1][i]]);
max[j][i] = Math.max(max[j-1][i], max[j-1][dp[j-1][i]]);
}
}
int K = Integer.parseInt(br.readLine());
for(int k = 0; k < K; k++) {
st = new StringTokenizer(br.readLine());
int res[] = lca(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
bw.write(res[0] + " " + res[1] + "\n");
}
bw.close();
}
}
3830: 교수님은 기다리지 않는다
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] par;
static long[] wei;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if( N ==0 && M==0) break;
par = new int[N+1];
wei = new long[N+1];
for (int i = 1; i <= N; i++) {
par[i]= i;
}
int a, b, w;
char cmd;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
cmd = st.nextToken().charAt(0);
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
if(cmd == '!') {
w = Integer.parseInt(st.nextToken());
union(a, b, w);
}
else {
if(find(a) != find(b)) {
sb.append("UNKNOWN\n");
} else {
long diff = wei[a] - wei[b];
sb.append(diff + "\n");
}
}
}
}
System.out.println(sb);
}
public static int find(int n) {
if (par[n]==n) {
return n;
}
int p = find(par[n]);
wei[n] += wei[par[n]];
par[n] = p;
return p;
}
static void union(int a, int b, int w) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return;
wei[pa] = wei[b] - wei[a] + w;
par[pa] = pb;
}
}
5719: 거의 최단 경로
import java.io.*;
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static final int MAXN = 500;
static int[] dist;
static int N, M, S, D;
static int[][] adj; //adjacent matrix
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
adj = new int[MAXN][MAXN];
dist = new int[MAXN];
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if(N == 0 || M == 0) return;
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) adj[i][j] = 0;
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
int u, v, p;
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
p = Integer.parseInt(st.nextToken());
adj[u][v] = p;
}
dijkstra(S);
removeShortest();
dijkstra(S);
if(dist[D] == INF) System.out.println(-1);
else System.out.println(dist[D]);
}
}
public static void dijkstra(int start) {
PriorityQueue<Route> pq = new PriorityQueue<>();
pq.add(new Route(start, 0));
Arrays.fill(dist, INF);
dist[start] = 0;
while(!pq.isEmpty()) {
Route cur = pq.poll();
if(dist[cur.v] < cur.weight) continue;
for(int i = 0; i < N; i++) {
if(adj[cur.v][i] == 0) continue;
int next = i;
int w = cur.weight + adj[cur.v][i];
if(dist[next] > w) {
dist[next] = w;
pq.add(new Route(next, w));
}
}
}
}
public static void removeShortest() {
Queue<Integer> q = new LinkedList<>();
q.add(D);
while(!q.isEmpty()) {
int cur = q.poll();
for(int i = 0; i < N; i++) {
if(adj[i][cur] != 0 && dist[cur] == dist[i] + adj[i][cur]) {
adj[i][cur] = 0;
q.add(i);
}
}
}
}
}
class Route implements Comparable<Route>{
int v;
int weight;
public Route(int v, int weight) {
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Route o) {
if(this.weight > o.weight) return 1;
else if(this.weight < o.weight) return -1;
else return 0;
}
}
17398: 통신망 분할
import java.io.*;
import java.util.*;
public class Main {
static int N, M, Q, X, Y;
static long sum;
static int arrQ[];
static boolean chk[]; // 처음 넣을 간선인지 아닌지 체크
static long cnt[];
static int par[];
static Edge edges[];
static int find(int n) {
if (par[n] == n) return n;
return par[n] = find(par[n]);
}
static void union(int a, int b) {
int findA = find(a);
int findB = find(b);
if (findA == findB)
return;
sum += (1L * cnt[findA] * cnt[findB]);
cnt[findB] += cnt[findA];
par[findA] = findB;
}
static class Edge {
int a, b;
public Edge(int a, int b) {
this.a = a;
this.b = b;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
edges = new Edge[M + 1];
sum = 0;
arrQ = new int[Q + 1];
chk = new boolean[M + 1];
cnt = new long[N + 1];
par = new int[N + 1];
for (int i = 0; i <= N; i++) {
par[i] = i;
cnt[i] = 1; // 처음 1로초기화
}
for (int m = 1; m <= M; m++) {
st = new StringTokenizer(br.readLine());
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
edges[m] = new Edge(X, Y);
}
Arrays.fill(chk, true);
for (int i = 1; i <= Q; i++) { // Q입력
st = new StringTokenizer(br.readLine());
int q = Integer.parseInt(st.nextToken()); // arrQ에 1번부터 Q의 정보 입력
arrQ[i] = q;
chk[q] = false; //제거 처리
}
for (int i = 1; i <= M; i++) {
if (chk[i] == true) { //마지막까지 제거되지 않은 간선이면 초기 union
int A = edges[i].a;
int B = edges[i].b;
union(A, B);
}
}
long temp = sum;
// Q를 마지막부터 꺼내면서 union하고 계산
for (int i = Q; i >= 1; i--) {
int N = arrQ[i];
int A = edges[N].a;
int B = edges[N].b;
union(A, B);
}
System.out.println(sum - temp);
}
}
'학습일지 > 삼성 SDS 알고리즘 특강' 카테고리의 다른 글
삼성 SDS 대학생 알고리즘 특강 10일차 - DP (0) | 2022.07.29 |
---|---|
삼성 SDS 대학생 알고리즘 특강 9일차 - DP (0) | 2022.07.28 |
삼성 SDS 대학생 알고리즘 특강 7일차 - 그래프 (0) | 2022.07.26 |
삼성 SDS 대학생 알고리즘 특강 6일차 - 그래프 (0) | 2022.07.25 |
삼성 SDS 대학생 알고리즘 특강 5일차 - 조합론 (0) | 2022.07.22 |