다락방

신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프다. 최소연결 : 간선의 수가 가장 적다 n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다. 그래프에서 일부 간선을 선택해서 만든 트리 특징 BFS,DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에서 많은 신장 트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. Spanning tree는 그래프에 있는 n개의 정점을 정확히 ..

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

B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다. 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다. 노드의 키가 x라면 자식의 수는 x+1개 이다. 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다. Key 검색과정 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고..

그래프(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..