justgo_developer

import java.util.*; public class Main {static int T;static int M;static int N;static int K;static int[][] map;static boolean[][] visit;static int[] dx = {0,1,0,-1};static int[] dy = {1,0,-1,0}; public static void main(String[] args) {Scanner sc = new Scanner(System.in);T = sc.nextInt();for(int i=0;i

Bellman-Ford 알고리즘 한가지가능의예일뿐 과정은 다를수 있다. Dijkstra의 알고리즘- 음수 가중치가 없다고 가정- s로뷰토의 최단경로의 길이를 이미 알아낸 노드들의 집합 s를 유지. 맨 처음엔 S={공징합}.- Loop invariant : S에 포함되지 않는 u에 대해서 d(u)는 이미 s에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단경로의 길이- d(u)가 최소인 노드 u(s에 속하지않고)를 찾고, s에 u를 추가- s가 변경되었으므로 다른 노드들의 d(v)값을 갱신 d(v) = min{d(v),d(u)+w(u,v)}즉, 에지(u,v)에 대해서 relaxation하면 Loop invariant가 계속 유지됨

import java.util.*; public class Main {static int N;static int M;static int [][] maze = new int[100][100];static boolean [][] visit = new boolean[100][100];static int[] dx = {0,1,0,-1};static int[] dy = {1,0,-1,0}; public static void main(String[] args) {Scanner sc = new Scanner(System.in);N = sc.nextInt();M = sc.nextInt();for(int i=0;i

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class Main {static int N;static int M;static int V;static int[][]G;static boolean[]visit;public static void dfs(int n){visit[n]=true;System.out.print(n+" ");for(int i=1; i

최단경로(shortest path problem)- 가중치(방향) 그래프 G=(V,E), 즉 모든 에지에 가중치가 있음- 경로 p=(v0,v1,...vk)의 길이는 경로상의 모든 에지의 가중치의 합- 노드 u에서 v까지의 최단경로의 길이를 S(u,v)라고 표시하자. 최단경로문제의 유형- Single-source(one-to-all) : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. ex)Dijkstra의 알고리즘- Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라./ single-source문제와 동일- Single-pair(one-to-one) : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라- ..

교착상태(Deadlock): 멀티프로세싱 환경에서 여러 프로세스가 간섭하여 생기는 문제-> 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태 Deadlock의 조건1. Mutual exclusion: 한번에 오직 하나의 프로세스만 자원을 사용가능2. Hold-and-wait: 프로세스가 할당된 자원을 점유하고 다른 프로세스가 반납하는걸 기다리는 상태3. No preemption: 프로세스의 할당된 자원은 강제로 빼앗을수 없다.4. Circular wait: 프로세스 자원요구가 순환적 Deadlock Prevention(데드락 예방): deadlock이 발생할 4가지 조건중 하나라도 제거하자1. Mutual Exclusion - 사용하지 않음/동시접근 허락되지 않음2. Hold and Wait..

prim의 알고리즘- 임의의 노드를 출발노드로 선택- 출발 노드를 포함하는 트리를 점점 키워 감- 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 가중치가 최소인 에지 찾기- VA: 이미 트리에 포함된 노드들- VA에 아직 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지- key(v) : 이미 VA에 속한 노드와 자신을 연결하는 에지들 중 가중치가 최소인 에지(u,v)의 가중치- ㅠ(v) : 그 에지 (u,v)의 끝점 u r:출발점 key값이 최소인 노드 찾기- 최소 우선순위 큐를 사용: V-VA에 속한 노드들을 저장: Extract-Min : key값이 최소인 노드를 삭제하고 반환

서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현배열 parent를 만들어 모든 트리를 하나의 배열로 표현 -자신이 속한 트리의 루트를 찾음FIND-SET(x)if x≠p[x]then p[x]

Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다.- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택하지 않는다.- n-1개의 에지가 선택되면 종료한다.노드가 9개이므로 에지가 8개까지만 하면 된다. 더하면 어짜피 사이클이 생김. ◆ 사이클 검사- 초기 상태 : 선택된 에지 없음- 각각의 연결요소를 하나의 집합으로 표현{a} {b} {c} {d} {e} {f} {g} {h} {i} MST-KRUSKAL(G, w)A

최소비용 신장 트리(MST) -입력 : n개의 도시, 도시와 도시를 연결하는 도로비용-문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. - 무방향 가중치 그래프 G=(V,E)- 각 에지 (u,v)∈E에 대해서 가중치 w(u,v)- 문제 : 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라.1. T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다.2. 가중치의 합이 최소가 된다. 싸이클이 없는 연결된 무방향그래프를 트리라고 부른다.MST 문제의 답은 항상 트리가 됨.노드가 n개인 트리는 항상 n-1개의 에지를 가짐 Generic MST 알고리즘- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될경우 에지(u,v)는 A에 대해서 안전하..