justgo_developer

페이징(Paging) 페이지 - 가상메모리를 일정한 크기로 나눈 블록프레임 - 물리메모리를 일정한 크기로 나눈 블록 페이지 테이블(page table)-각 페이지에 대한 프레임위치를 가지고 있다.- 메모리 주소는 페이지 번호와 옵셋(offset)으로 구성된다. 페이징은 외부단편화가 없다.No external fragmentation - address : n+m bits- n : page number- m : offset Segmentation -가상메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할하고 메모리를 할당하여 주소 변환을 한다.- 세그먼트번호와 옵셋(offset)으로 구성된다.- 모든 세그먼트들은 동일하기 않기 때문에 세그멘테이션기법은 동적분할과 비슷하다.- No internal frag..

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

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..

서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현배열 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