시냅스

Spanning Tree (신장 트리) Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히..

이진 탐색 트리, 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, 덱 Deque https://liltdevs.tistory.com/85 [자료구조] 큐, Queue - 배열리스트로 구현 큐, Queue 큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 q liltdevs.tistory.com 덱(deque, "deck"과 발음이 같음 ← double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 큐 구현 Queue using linekd..

큐, 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 스택 생성 ..

다항식 이중 연결리스트 다항식의 항은 계수 + 차수로 이뤄진다. 단 각 항은 내림차순 정렬로 가장 큰 차수가 header node가 된다. 정렬은 node를 생성하면서 조건문을 통해 앞이나 뒤에 넣을 수 있게 하였다. 단, 이 때 차수가 같은 노드가 추가되면 새로 node를 생성하지 않고 기존 Node에 연산만을 할 수 있게 하였다. 계산의 경우에는 덧셈 뺄셈과 곱셈 나눗셈을 따로 분리하여 생각하여야 한다. 덧셈, 뺄셈의 경우 같은 차수에서만 연산이 이뤄지면 되는데, 곱셈, 나눗셈의 경우에는 매 항마다 연산이 이뤄져야 한다. 또한 계수가 0일 경우에는 해당 항이 지워질 수 있게 하였다. 구현 리스트 생성 원소 추가 원소 반환 제거 연산 생성 typedef struct ListNodeType { int c..

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

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