다락방

2. 프로세스 프로세스는 실행 중인 프로그램으로 정의한다. 운영체제는 CPU를 가상화시켜 환상을 만들어 낸다. 시분할(time sharing)이라고 불리는 이 기법은 원하는 수 만큼 프로세스를 동시에 실행 할 수 있게 한다. 시분할 기법은 CPU를 공유하기 때문에 각 프로세스의 성능은 낮아진다. 운영체제의 지능은 정책(Policy)의 형태로 표현된다. 정책이란 운영체제에서 어떤 결정을 내리는데 사용되는 알고리즘이다. 다수의 실행 가능한 프로그램이 있을 때 운영체제의 스케줄링 정책(Scheduling Policy)이 이러한 결정을 내린다. 2.1 프로세스의 개념 운영체제는 실행 중인 프로그램의 개념을 제공하는데, 이를 프로세스라 한다. 프로세스의 구성요소를 이해하기 위해 하드웨어 상태(machine sta..

트라이(Trie) 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색등 문자열을 탐색하는데 특화 되어있는 자료구조 래딕스 트리(radix tree) or 접두사 트리 (prefix tree) or 탐색 트리(retrieval tree) 라고도 한다. 트라이는 retrieval 에서 나온 단어다. 트라이 장단점 장점 트라이는 문자열 검색을 빠르게 한다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 더 효율적이다. 단점 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장공간의 크기가 크다는 단점도 있다. 트라이의 생성 시간복잡도는 O(MxL): 탐색 시간복잡도 O(L) 가..

그래프(Graph) 그래프의 정의와 특징 정의 그래프는 정점(vertex)와 그 정점을 연결하는 간선(Edge)으로 구성된다. 이러한 정점과 간선의 집합으로 이루어진 자료구조를 그래프라고 한다. 그래프 용어 정점(Vertex) : 노드(Node) 라고도 하며 데이터가 저장되는 그래프의 기본 원소이다. 간선(Edge) : 링크(Link) 라고도 하며 정점간의 관계를 나타낸다. 인접정점(Adjacent Vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다. 차수(Degree) : 정점에 연결된 간선의 수, 무방향 그래프에서 하나의 간선은 두개의 정점에 인접하기에 간선 수에 2배를 해주면 된다. 방향 그래프의 경우 외부에서 오는 간선의 수를 진입차수(in-degree)라고 하며, 외부로 향..

연결리스트(Linked_List) 동적으로 크기가 변할 수 있고, 삭제/삽입 시 데이터를 이동할 필요가 없는 연결된 표현(linked representation) 데이터를 한 군데 모아두지 않고, 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법 포인터(pointer)를 통해 데이터를 연결 연결리스트에서 각각의 원소(element)를 노드(node)라고 한다. 노드는 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터(pointer)를 가지고 있다. 맨 앞 노드를 head node 맨 뒤를 tail node 라고 한다. 또 각 노드에서 바로 앞쪽 노드를 predecessor node 바로 뒤쪽 노드를 successor node 라 한다. 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조를..

리스트(List) 리스트(list) 혹은 선형 리스트(linear list)란, 순서를 가진 항목들의 모임을 뜻한다. 리스트란 자료를 나열하여 저장하는 ‘목록’ 형태 리스트의 항목들이 순서/위치 를 가진다 스택, 큐 자료구조도 리스트의 일종이다. 순서 개념이 없는 집합(set)과 차이가 있다. 배열(Array) 또는 연결리스트(Linked_list)를 통해 구현 가능하다. 배열(array) - 타입이 같은 데이터를 하나로, 연속적인 메모리 공간, 인덱스(index) 번호를 사용해 쉽게 접근가능 같은 형태의 변수 여러 개 만들 때 사용 반복 코드 등에서 효율적이다. 구조체(struct) - 타입이 다른 데이터를 하나로

큐(Queue) 큐(Queue)는 데이터를 임시저장 하는 자료구조이다. 선입선출(FIFO:First In First Out)방식이다. 가장 먼저 들어온 데이터가 가장 먼저 나간다. 큐에 데이터를 추가하는 작업을 인큐(enqueue)라고 하고 ,꺼내는 작업을 디큐(dequeue)라고 한다. 데이터를 넣는 쪽을 리어(rear) 꺼내는 쪽을 프런트(front)라고 한다. 가득 찬 큐에 요소를 추가하려고 할 때 overflow 가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 underflow가 발생한다. enqueue 및 dequeue 작업이 있는 경우 어느 시점에서 큐가 비어있어도 자료를 삽입하지 못하는 경우가 발생한다. 함수 enque() - 데이터 넣기 deque() - 데이터 꺼내기 peek() - 데..

스택(Stack) 스택(stack)은 데이터를 임시 저장할 때 쓰는 자료구조이다. 후입선출(LIFO:Last In First Out) 방식이다. 가장 최근에 들어온 데이터가 가장 먼저 나간다. 스택에 데이터를 넣는 작업을 Push라고 하고 반대로 데이터를 꺼내는 작업을 Pop이라고 한다. 스택배열(stk) - list형 배열 스택크기(capacity) - 스택의 최대 크기를 나타내는 int형 정수 스택포인터(ptr) - 스택에 쌓여있는 데이터의 개수를 나타내는 정수 값 스택의 구조&사용 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 요긴하게 사용하는 자료구조이다. 문서 편집기에서 undo(되돌리기) 같은 경우 이 스택 자료구조를 사용한다. 시스템 스택 함수호출 시스템 스택(system st..