OS Objectives 1) Convenience: 편리성 2) Efficiency: 효율성 3) Ability to evolve: 발전 가능성 Role of OS - User / Computer Interface - I/O device control, file management, program create 등을 도움 - 자원 관리자 Evolution of OS OS에 필요한 서비스에 의해 하드웨어에 추가되기도 함 Serial Processing: 순차 처리 - No OS 1) 수동으로 카드 로드 2) Job to Job Transition - 모든 활동이 순차적 Problems 1) High Setup Time -> 준비 시간이 길었다. 2) Scheduling time -> 현대 CPU 스케줄링이..
전체 글
spypsyMemory: Stores data and programs 1) Capacity (용량) 2) Cost (per bit) (비용) 3) Access time (속도) modern 1) Smaller, more expensive, fast -> SRAM 2) Larger, cheaper, slower -> DRAM Memory Hierarchy 빠른 것을 CPU 근처에 (SRAM) -> 하위 계층까지 접근하지 않도록 발전 -> 상위계층 극대화, 하위계층 최소 Locality of reference : 참조의 지역성 / 지역성의 원리 - 프로그램은 상대적으로 적은 부분의 주소를 접근하려는 경향이 있다. - 이 부분은 프로그램이 실행될 때마다 변한다. 1) Temporal locality (locality i..
Basic component: CPU, I/O module, bus, memory Evolution of processor -> 폰 노이만 구조의 한계를 벗어나지 못함 실행 시 메모리에 적재되어야하는데, 버스가 너무 많이 실행됨 Memory Static RAM -> Cache : 6 transistor, Expensive, high speed, no fresh required Dynamic RAM -> Main Memory : one transistor + one capacitor, slower than SRAM, dynamic refresh required Heterogeneous Memory 1) Load and Execute -> 자주 쓰이는 모델 / hot, cool data 사용 2) Direc..
https://www.acmicpc.net/problem/1736 1736번: 쓰레기 치우기 방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레 www.acmicpc.net 4637번: Robots 위의 문제와 상당히 유사한 문제이다. 접근했던 방법은 로봇이 오른쪽과 아래만 움직일 수 있으므로 x나 y 방향으로 감소할 수 없다는 점을 이용했다. 만약 현재 로봇이 (4, 6)에 위치한다면 당연히 (4, 7) 또는 (5, 6)으로 이동을 할 것이고, 최소의 로봇 개수를 파악해야하므로 먼저 위에서부터 채우는 방식으로 접근했다. ..
https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 세그먼트 트리 응용 문제 세그먼트 트리를 이용해 구간 합을 미리 구하거나 최솟값을 적는 등으로 활용이 가능했으나, 해당 문제에서는 tree[node]에 가장 작은 값의 인덱스를 집어 넣어 문제를 해결할 수 있다. 원리는 아래와 같다. 예제로 살펴보면, 먼저 가장 작은 값의 인덱스인 1을 기준으로 히스토그램의 넓이를 구한다. 이후 1의 왼쪽과 오른쪽을 다시 기준으로 ..
https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 처음에 0이 존재 다음에는 이를 비트반전 시킨 문자열을 뒤에 추가한다. 이를 무한으로 반복했을 때 N번째 자리의 숫자를 구하는 문제 0 01 0110 01101001 0110100110010110 ... 이렇게 증가하는데, 여기에는 규칙이 있다. 만약 N번째 자리의 수를 구한다면, N번째 자리의 숫자는 N - 2^x의 숫자를 반전 시킨 값이다. N - 2^x는 1이 되거..
https://www.acmicpc.net/problem/26093 26093번: 고양이 목에 리본 달기 첫 번째 줄에는 고양이의 수 $N$과 리본 종류의 수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 100, 2 \leq K \leq 10\,000)$ 다음 $N$개의 줄에는 각각 $K$개의 정수 $a_{i,1}, \cdots, a_{i,k}$이 공백으로 구 www.acmicpc.net 양 옆에 위치한 고양이와 방울의 종류가 같지 않도록 함과 동시에 만족도를 최고로 높이는 방법을 찾아야한다. 그래서 접근한 방법은 단순히 이전 고양이의 가장 높은 만족도의 방울 번호와 다음으로 높은 만족도의 방울 번호를 저장하여 현재 순서의 고양이의 방울 번호와 비교하여 만족도의 합을 저장하는 방식이..
https://www.acmicpc.net/problem/27651 27651번: 벌레컷 크기 $N$의 $1$차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배 www.acmicpc.net 주어진 수열을 3분할하는데, 이를 각각 머리, 가슴, 배라고 지칭한다. 1 ~ x 의 크기 < y + 1 ~ n의 크기 < x + 1 ~ y 를 만족하는 수열의 개수를 구해야한다. 즉, 머리 < 배 < 가슴을 만족해야한다. 이를 위해 우선 1 ~ n까지의 수열의 합을 배열에 저장해주어 중복으로 덧셈을 실시하는 일이 발생하지 않도록 누적합을 이용했다. 먼저 1 ~ x를 구하는 것은 간단하다. 단..