비연속 할당 사용자 프로그램을 여러 개의 block으로 분할한다 (Paging, segmentation) 실행 시 필요한 block만 메모리에 적재한다 (나머지는 swap device에 존재) 프로세스를 통째로 올리지 않고 일부만 올려놓고 사용한다 기법 paging system segmentation system hybrid paging/segmentation system Address Mapping 주소 매핑 가상 주소 = 상대 주소 = 논리주소: 연속된 메모리 할당을 가정한 주소 실제주소 = 물리주소 = 절대주소: 실제 메모리에 적재된 주소 Address mapping: 가상 주소를 실제 주소로 매핑하는 작업 Block Mapping 사용자 프로그램 block 단위로 분할 및 관리 Virtual Ad..
메모리(기억 장치 종류) 레지스터 -> 캐시 -> 메인 메모리 -> 보조기억장치 (계층 구조) 왼쪽으로 갈수록 비싸지고 용량이 작고 빠르다 I/O 병목현상 해결하기 위한 계층구조이다 레지스터와 캐시는 CPU 내부에 존재하여 HW가 관리하고 나머지 메모리 종류는 SW(OS)가 관리한다. Block단위 하드디스크 (보조 기억장치)에서 메모리로 데이터를 올릴 때 1비트를 읽더라도 효율성을 위해 해당 1비트만 가가져오는 것이 아니라 block단위로 데이터를 읽어온다. (보통 1~ 4kb) word 단위 메인 메모리에서 레지스터로 데이터를 word 단위로 읽어온다. 컴퓨터에서 32비트, 64비트 시스템은 워드 단위이다. Address Binding 프로그램의 논리 주소(cpu가 생성하는 주소)를 실제 메모리의 물..
www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 10진수로 변환할 때 int범위를 넘어갈 수 있기 때문에 8진수를 바로 2진수로 바꿔주는 문제이다. 8진수 3자리는 2진수 1자리가 된다는 것을 이용한다. 맨 앞자리의 수가 0으로 시작할 경우를 주의해준다 import java.util.Scanner; public class Main { static String num; static String[] binary= {"000","001","010","011","100","101","110","111"}; //8보다 작음 public static void main(Stri..
www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net m개의 통로가 연결되어있다고 해서 이미 연결된 간선의 수 (cnt) = m으로 초기화했다가 틀렸다. 주어진 연결된 통로가 중복되거나 사이클을 형성하지 않도록 m개의 통로도 union-find 함수를 이용해서 연결해주어야한다. 그 다음에는 순차대로 거리가 작은 순으로 그래프에 추가해준다. import java.util.ArrayList; import java.util.Collection..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 뒤에 1을 붙여주는 연산은 숫자 x*10+1 이라서 정수 범위 대략 2*10^9을 넘어가서 런타임에러가 난다. long형으로 바꿔줘야 된다. import java.util.Scanner; public class Main{ static long a,b; static long answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in); answer=-1; a=sc.nextInt(); b=sc.nextInt(); go(a,b,0); if(answer==..
www.acmicpc.net/problem/1755 1755번: 숫자놀이 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 www.acmicpc.net 숫자와 원하는 형태로 변환한 문자열을 같이 넣고 문자열의 사전순으로 정렬한 뒤 출력한다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Word implements Comparable{ String word;//규칙에 따라 문자열로 변환된 숫자 ..
www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 왠지 dp문제인 거 같은데 어떻게 업데이트할지 몰라서 반복문으로 돌리며 나오는 경우의 수를 arraylist에 넣고 flag변수로 해당 구슬 무게가 되는지 확인했다 다행히 통과 import java.util.ArrayList; import java.util.Scanner; public class Main { static int n,m;// 추의 개수 구슬의 개수 static int[] chu;//추 static ..
www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 두 개의 마을로 나눈다고 SUBSET하고 뻘짓하다가 시간초과났다 ㅎ 일 단 MST로 연결하되, 모든 정점을 연결한 상황에서 가장 가중치가 큰 길 하나만 없애면 자동으로 두 마을로 나뉘게 된다. 즉 간선을 하나 없앤다 => 간선 개수가 N-2개가 될 때까지만 UNION-FIND해준다. import java.util.Arrays; import java.util.Scanner; ..
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import java.util.Scanner; public class Main { static int n; static int[][] cost; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); cost=new int[n][n]; for (int i = 0; i
www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1-> a -> b -> n 경로와 1-> b -> a -> n 경로 중 작은 것이 답이다. 중간에 이어지는 선이 없으면 경로가 없는 것이다. import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class Edge impl..