justgo_developer

최단경로(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까지의 최단 경로를 찾아라- ..

memory partitioning - Fixed partitioning(고정분할): 시스템 설계 시 , main memory를 고정된 크기로 분할 프로그램 작을떄도 전체적인 부분을 차지한다. 내부단편화(internal fragmentation)이라고 한다.- Dynamic partitioning(동적분할): 프로세스 크기에 맞게 분할 메모리에 고정된 공간에서 동적인 할당을 받고, 메모리가 꽉차면 스왑아웃을 통해 그곳에 계속 프로세스가 스왑이 되므로, 외부 단편화(external fragmentation)이 발생 외부단편화를 극복하기 위해 메모리 집약(compaction) 사용프로세스들을 이동시켜 연속적으로 만들고 메모리의 모든 빈공간은 한블럭이 된다. - Dynamic partitioning place..

교착상태(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에 대해서 안전하..

import java.util.*; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {Queue q = new LinkedList();int N = sc.nextInt();for(int i=1;i

DAG는 방향 사이클이 없는 방향 그래프.ex)작업들의 우선순위 위상정렬(topological ordering)-DAG에서 노드들의 순서화 v1,v2 ....vn, 단, 모든 에지(vi,vj)에 대해서 i

import java.util.*; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int M = sc.nextInt();int[] cup = new int[4];cup[1]=1;for(int i=0;i