with with

- 그래프 노드와 노드를 연결하는 간선들로 이루어진 비 선형 자료구조로 트리와 다르게 패턴이 없다. 모든 노드가 1-1로 연결되어 있는 그래프를 완전 그래프 (Complete Graph)라 부르고, 원래 그래프에서 일부 간선을 제외한 그래프를 부분 그래프 (Subgraph)라 부른다. 그래프의 표현 방법은 인접 행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List)로 표현할 수 있는데, 인접 행렬로 표현시 구현이 쉽고, 특정 노드간의 인접 여부 확인이 빠르다는 장점이 있지만, 특정 노드와 인접한 모든 노드를 알고자 할 때, 모든 간선을 확인해야 하고, 구현상의 이유로 메모리 낭비가 발생한다는 단점이 있다. 반면에 인접 리스트로 표현시 메모리 효율적이고, 인접한 노드를 효율적으..

- 스택 (Stack) 한 쪽에서만 데이터 입출력이 일어나는 선형구조로, 가장 마지막에 삽입된 원소가 가장 먼저 제거되는 LIFO 형태의 자료구조 이다. c++ STL의 stack 라이브러리이다. 위 코드는 일반 스택1과, 크기가 2, 값 100으로 초기화한 vector을 이용한 스택2를 수정해보는 코드이다. - 큐 (Queue) 한 쪽에서 데이터 입력이, 다른 한 쪽에서 데이터 출력이 일어나는 선형구조로, 가장 처음에 삽입된 원소가 가장 먼저 제거되는 FIFO 형태의 자료구조 이다. c++ STL의 queue 라이브러리이다. 위 코드는 일반 큐1과, 크기가 2, 값 100으로 초기화한 list을 이용한 큐2를 수정해보는 코드이다.

트리에 대한 이론적인 부분은 세 번에 걸쳐 포스팅한 바 있다. Tree 트리구조는 아주 중요한 알고리즘이라 세 번에 나누어서 진행할 예정이다. Tree... 이게 얼마나 사기(?)냐 하면은 트리를 이용하여 데이터를 관리할 경우 데이터 탐색에 필요한 시간이 O(n^2)에서 O( with611.tistory.com Tree - Binary Search Tree Binary Tree 중, 아래의 조건을 만족하는 Tree이다. 1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다. 2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다. BST로 with611.tistory.com Tree - Heap, B-Tree Heap Heap은 complete binary tree의 일종으로 추..

연결 리스트는 데이터와 포인터를 가진 노드들이 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. vector와 같은 배열과 다르게 리스트의 중간 지점에서도 자료의 추가와 삭제가 빠르고, 메모리 선할당이 없고, 크기도 마음대로 정할 수 있을 뿐더러, 데이터의 추가/삭제시에도 이터레이터가 유효하다는 장점이 있지만, 랜덤 액세스가 느리다는 단점이 있다. 노드들이 포인터를 이용해서 연결되어 있는 방식에 따라 다음의 세 종류로 분류된다. - 단일 연결 리스트 (Singly Linked List) 각 노드에 데이터와 하나의 포인터가 있고, 각 노드는 다음 노드를 가리키는 구조이다. - 이중 연결 리스트 (Doubly Linked List) 각 노드에 데이터와 두 개의 포인터가 있고, 각 노드는 이전과 다..

- 정적 배열 (Static Array) 크기가 고정되어 있는 배열로 저장할 수 있는 데이터의 개수가 고정되어 있다. 한 번 할당하면 메모리를 추가적으로 할당하거나 해제하지 않아도 되고, 랜덤 액세스 속도가 빠르다는 장점이 있지만, 필요에 따라 크기를 조절할 수 없고, Stack영역에 할당되기 때문에 최대 크기의 제약이 있다는 단점이 있다. c++ STL의 array 라이브러리이다. 위 코드는 4행 8열의 배열을 생성한 후 이터레이터를 이용해서 탐색하는 코드이다. - 동적 배열 (Dynamic Array) 크기가 유동적으로 변하는 배열. 필요에 따라 배열의 크기를 조절할 수 있다는 장점이 있지만, 배열의 크기를 조절할 때 마다 메모리를 추가적으로 할당하기 때문에 퍼포먼스 이슈가 발생할 수 있다. c++ ..

- 공유 메모리 공유 메모리는 프로세스 간 통신을 위한 메커니즘 중 하나로, 여러 IPC 중 가장 빠른 수행속도를 보여준다. 하나의 메모리 영역을 서로 다른 프로세스가 접근하게 되어, 데이터 복사와 같은 불필요한 오버헤드가 발생하지 않기 때문이다. 단, 동기화 기능을 제공하지 않기 때문에, 세마포어, 뮤텍스 등의 메커니즘을 이용하여 메모리 영역 접근을 동기화 해야한다. - 공유 메모리 함수 1. key_t ftok(const char *pathname, int proj_id); 2. int shmget(key_t key, size_t size, int shmflag); 공유 메모리를 생성하고 접근할 수 있는 식별자를 반환한다. 3. void *shmat(int shmid, const void *shmad..

- 메세지 큐 메세지 큐는 프로세스 간 통신을 위한 메커니증 중 하나로, 지명 파이프와 유사하다. 큐(Queue) 데이터 구조로 관리하며, 커널에서 전역적으로 관리되기에 모든 프로세스에서 접근이 가능하다. 메세지 큐의 접근자를 아는 모든 프로세스가 동일한 메세지 큐에 접근하여 데이터를 공유할 수 있어, 다른 IPC 메커니즘에 비해서 사용법이 매우 직관적이고 간단하다. 여러 프로세스가 메세지 큐에 접근할 때, 각 메세지 유형을 지정하여 접근해야 하기에, 각 프로세스가 필요로 하는 메세지만 가져올 수 있다. 단, 하나의 메세지 스택(박스)를 분할하여 가져오는 방식은 안된다. (파이프에서 스트림 형태로 가져온 것과는 대조) - 메세지 큐 함수 1. key_t ftok(const char *pathname, i..

- 파이프 파이프는 프로세스간 통신을 위한 메커니즘 중 하나로, 프로세스의 데이터 흐름을 다른 프로세스로 연결할 때 사용한다. (주로 한 프로세스의 출력을 다른 프로세스의 입력으로 연결) 동일한 부모 프로세스로 부터 생성된 자식 프로세스 사이(부모-자식간 통신)에서만 사용 가능하며, 익명 파이프라고도 불린다. 파이프는 프로세스 사이에 형식이 없는 데이터의 교환을 가능케 하는데, 파이프를 통해 전달되는 데이터는 단순한 바이트 스트림의 형태이다. 파이프는 4kb의 고정된 크기(용량)을 갖는데, 만약 입력되는 데이터의 크기가 파이프 버퍼(4kb)보다 크다면 interleaving, 즉 데이터를 쪼개어 분할 전송하게 된다. 만약 입력되는 데이터의 크기가 파이프 버퍼보다 작다면 atomic, 즉 확실히 데이터를 ..