파게로그

1.2 Computer-System Organization 1.2.1 Computer-System Operation 1개 이상의 CPU와 많은 디바이스 컨트롤러들은 공유 메모리로의 접근을 제공하는 common bus를 통해 연결되어 있다. 각 디바이스 컨트롤러는 디스크 드라이브, 오디오 디바이스, 비디오 디스플레이와 같은 특정한 유형의 장치를 책임진다. CPU와 장치 컨트롤러들은 memory cycle를 얻기 위해 경쟁하며 parallel하게 실행될 수 있다. 공유 메모리로의 순서대로의 접근을 보장하기 위해 메모리 컨트롤러는 메모리로의 접근을 synchronize한다. 컴퓨터가 켜지면 - 펌웨어라고 알려진 bootstrap program(ROM이나 EEPROM에 저장되어 있음)이 CPU 레지스터, 장치 ..

PART One: Overview Chapter One: Introduction 1.1 What Operating Systems Do 큰 틀 잡기 좋은 자료들 위키백과 - 시스템 소프트웨어 학문명백과 - 운영체제 IT용어사전 - 운영체제 운영체제의 정의 컴퓨터의 하드웨어를 관리하는 프로그램 운영체제의 역할 사용자가 편리하고(convenient) 효율적인(efficient) 방식으로 프로그램을 실행할 수 있는 환경 제공 컴퓨터의 자원을 관리함 '실행 관리자'로서 하드웨어와 소프트웨어를 관리함 응용 프로그램 실행 환경 제공 user와 하드웨어 사이의 매개체로서의 역할 누가 시스템을 사용할 수 있는지를 관리함 어떻게 시스템을 사용할 수 있는지를 관리함 user program이 시스템의 작동을 방해하지 않도록 ..

퀵 정렬은 말 그대로 대부분의 경우에 최상의 성능을 보여주는 정렬 기법이라고 할 수 있다. 정렬은 다음과 같이 이루어진다. 1. 리스트에서 임의의 한 원소를 pivot으로 하여, 이를 기준으로 두 리스트로 나눈다. 리스트의 크기는 다를 수 있다. 2. 왼쪽 리스트에는 pivot보다 작은작거나 같은 값만을, 오른쪽 리스트에는 pivot보다 큰크거나 같은 값만을 남긴다. 3. 왼쪽 리스트와 오른쪽 리스트에 대해서 quick sort를 수행한 후 이를 병합한다. 여기서 2번 과정은 다음과 같이 이루어진다. [3, 6, 1, 8, 5, 9, 4, 2, 7]을 예로 들고 pivot은 항상 첫 번째 원소라고 하자. 1. arr = [6, 1, 8, 5, 9, 4, 2, 7], pivot = arr[first] = ..

insertion sort는 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 굉장히 유사하다. 하나의 카드를 잡아서, 왼쪽부터 훑어나가면서 카드를 원하는 위치에 쏙 하고 집어넣기 때문이다. 다만 실제 구현에서는, 리스트에서 원소를 밀어주는 것이 꽤나 부담스럽게 다가온다. 0. i=1일 때, arr[1]은 이미 정렬된 상태이다. 1. i=2일 때, key = arr[2] key를 arr[1]과 비교하여 올바른 위치에 넣되, arr[1] 자리에 들어가야 한다면 원래 arr[1]을 뒤로 밀어낸다. 이 때 arr[0]까지 갈 수도 있다. 올바른 위치에 넣는다는 것은, arr[j]가 arr[i]보다 작을 때, 밀어내기를 중단하는 것이다. arr[0]~arr[i-1]은 이미 정렬된 리스트이지만 key는 완전히 새..

divide&conquer 방식의 알고리즘으로서 일반적으로 재귀 호출을 통해서 구현된다. 과정은 다음과 같다. 1. 리스트의 길이가 1 이하이면 이미 정렬된 리스트이다. 2. 정렬되지 않은 리스트를 동일한 또는 비슷한 크기의 두 개의 부분 리스트로 분할한다. (divide) 3. 각 부분 리스트를 재귀적으로 merge sort를 이용하여 정렬한다. (conquer) 4. 두 부분 리스트를 하나의 리스트로 병합한다. (combine) [5, 2, 4, 7, 6, 1, 3, 8] [5, 2, 4, 7] / [6, 1, 3, 8] [5, 2] / [4, 7] // [6, 1] / [3, 8] [5] / [2] // [4] / [7] /// [6] / [1] // [3] / [8] ↑divide ↓conquer..

bubble sort는 '정렬' 하면 빠질 수 없는 가장 무지막지한(?) 방법이라고 생각한다. 방법은 첫 번째 원소부터 마지막 원소까지 비교해감으로써 한 개의 원소를 정렬하고, 이 과정을 마지막 원소까지 반복하는 것이다. 시간복잡도 - 비교 횟수 i=0일 때 n-1번, 1일때 n-2번, ... 이렇게 해서 n(n-1)/2 - 교환 횟수 최악의 경우는 원소가 역순으로 정렬된 경우이고, n(n-1)/2회가 발생한다. (temp를 이용하는 swap()을 생각한다면, 3*n(n-1)/2회가 발생함) 최상의 경우는 원소가 정렬된 경우이고, 0회가 발생한다. - T(n) = O(n^2) def bubble_sort(arr): # 배열의 범위를 설정 # last는 마지막 원소의 index for last in ran..

스트림(Stream)이란? 여기서 말하는 스트림은 Java 8에서 추가된 Stream API와는 무관하다. 스트림이란, 연속된 데이터가 단방향으로 흐름을 추상화한 것이다. 문자 그대로 '물의 흐름'을 떠올리면 쉬운데, 출발지로부터 도착지까지의, 방향이 하나로 일정한 흐름이다. Java에서는 입출력 스트림 외에도 바이트 기반 스트림, 보조 스트림, 문자 기반 스트림이 제공된다. 스트림은 마치 큐(queue)처럼 FIFO(First In, First Out) 구조를 가져서, 스트림 속 데이터의 순서를 바꿀 수 없다. 입출력 스트림이란? Java에서는 입출력을 처리하기 위한 입출력 스트림을 제공하고 있다. InputStream의 경우 출발지는 키보드, 마우스와 같은 Input 장치나 다른 프로그램 등이고 도착..

정수에 대한 접두사와 접미사 2진법 0b11010 8진법 032 10진법 26 16진법 0x1a public class IntegerSystemTest { public static void main(String[] args) { System.out.println(0b1010); // 10 System.out.println(10); // 10 System.out.println(012); // 10 System.out.println(0xA); // 10 } } 긴 정수(8byte) long n1 = 26L; long n2 = 0x1aL; 실수 123.4 // 8byte(double형) 123.4f // 4byte(float형) 123.4d // 8byte(double형) 1.234e // 부동 소수점형, 지..