시냅스

이진 탐색 트리, Binary search tree 이진 탐색 트리는 각 노드에는 값이 있다. 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다. 이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다. 다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다. 이 경우 red black tree를 이용할 수 있다. 아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다. 구현 생성 삽입 개별 node 삭제 Tree 삭제 생성 typedef struct BinSearchTreeNodeType..

힙 Heap 힙은 항상 완전 이진 트리 (위로부터 왼쪽 오른쪽 순서대로 쌓이는 것을 말한다.)의 형태를 지닌다. 부모의 값은 자식의 값보다 크거나(Max heap), 작아야(Min heap) 한다. 따라서 루트노드에는 항상 데이터 중 크거나 작은 값이 저장되어 있기 때문에 최대, 최소값 탐색에 O(1)이 걸린다. 데이터의 삽입과 삭제는 모두 O(log N)이 소요된다. 이러한 특성은 완전 이진 트리이며, 부모노드가 항상 크거나 작다는 확증에 기인한다. Max heap 구현 생성 삽입 root node 반환, Pop Heap 삭제 생성 typedef struct HeapNodeType { int key; } HeapNode; typedef struct HeapType { int maxElementCount..

트리 Tree 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. 용어 정리 node(노드) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다. Ed..

큐, Queue 큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리(I/O)나 윈도 시스템의 메시지 처리기, 프로세스 관리 (CPU Schduling) 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 배열리스트로 구현하는 queue는 선형 큐와, 환형(원형) 큐로 나눌 수 있다. 선형 큐는 막대..

스택 Stack 스택(stack)의 접근은 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 연결리스트를 활용한 스택과 배열리스트를 활용한 스택의 차이점을 아래에서 알아본다. 구현 스택 생성 Push Pop Peek 제거 배열리스트를 활용한 Stack, ArrayStack 스택 생성 ..

이중 연결 리스트 (Doubly Linked list) 이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 탐색에서는 단일 연결 리스트보다 시간적 우위를 지닌다. 기준에 따라 Head에서 출발하거나, Tail에서 출발하는 것이 가능하다. 단, 각 노드의 관리에 유의해야 하기 때문에, 작업량이 많아지고 자료구조의 크기와 사용 메모리가 증가한다. 특징 탐색에 용이하다. 자료구조의 크기가 증가한다. 메모리 사용량이 증가한다. 단일 연결 리스트보다 관리에 유의해야 한다. 이 외에는 단일 연결 리스트와 비슷한다. 단일 연결 리스트 구현 리스트 생성 원소 추가 원소 반환 원소 제거 리스트 제거 리스트 생성 typedef stru..

원형 연결 리스트 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. 단일 연결 리스트와 동일한 특징을 갖지만, 가장 첫 노드와 끝 노드가 연결된다는 특징을 갖는다. 원형 연결 리스트는 Cpu scheduling 에서 Ready queue나 스트림 버퍼를 구현하는 데에 많이 사용된다. 단, header는 tail과 동일하여 list의 0번째 node는 header의 다음 node가 된다. 특징 노드를 탐색하면서 순회에 용이하다. 반복적인 순회에서 끝을 확인해야할 필요가 없음. header 다음 node가 0번째 node가 된다. 이외에는 단일 연결리스트와 동일하다. 단일 연결 리스트 구현 리스트 생성 원소 추가 원소 반환 원소 제거 리스트 제거 리스트 ..

단일 연결 리스트 (Singly Linked List) 단일 연결 리스트는 각 노드들이 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. (다만, 오늘 구현할 것은 tail을 갖지 않는 linked list로 1번의 반복문을 거치게 된다.) 다만, 기존 링크를 해제하거나 삽입할 때에는 기존 링크의 전이나 다음 노드 관리에 대해 유의해야 한다. 또한 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 특히 단일 연결 리스트는..

배열 리스트 (Array List) 배열리스트는 자료를 순서대로 저장하는 자료구조로, 논리적 순서(저장)와 물리적 순서(저장)가 동일하다. 원소의 위치 인덱스는 0부터 시작하고, 정적배열로 최대 갯수가 정해져 있고,이는 배열과 동일하다. C에서는 라이브러리로 배열리스트를 지원하지 않기 때문에, 개발자가 직접 구현해야하는 기능으로는, 리스트 생성 원소 추가 원소 추가 가능 여부 판단 원소 반환 원소 제거 리스트 초기화 리스트 삭제 를 꼽을 수 있다. 특징 저장순서가 순차적이기 때문에 Index가 곧 위치로, 탐색(O(1))에 용이하지만, 배열이 공백을 허용하지 않아 삽입이나 삭제 시에는 노드가 끊기지 않아야 하기 때문에, 삽입이 됐을 떄에는 기존 노드를 뒤로 미루거나, 삭제가 됐을 때에는 원래 노드들을 앞..