justgo_developer

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

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

가상메모리: 한정된 물리 메모리의 한계를 극복하고자 디스크와 같은 느린 저장장치를 활용해, 더 많은 메모리를 활용할 수 있게 해 주는 것 Principle of Locality(지역성의 원리): 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나,최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음. *Principle of Locality라는 특성 덕분에 virtual memory가 효과적으로 운영 가능 Thrashing(쓰레싱): 너무 자주 페이지 교체가 일어나는 현상. 어떤 프로세스가 계속적으로 페이지 부재가 발생하여 프로세스의 처리시간보다 페이지 교체 시간이 더 많아 지는 현상 ■ Paging - simple paging 기법에 비해 page number에 해당하는 bit수가 많아졌다...

Floyd-warshall algorithm(all-to-all) - 가중치 방향 그래프 G=(V,E) , V={1,2,...n}- 모든 노드 쌍들간의 최단경로의 길이를 구함- d^k[i,j] : 중간에 노드집합 {1,2,....k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이경로찾기 경로출력하기

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가 계속 유지됨

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