“우리 대부분은 초라한 옷차림과 엉터리 가구들을 부끄럽게 여기지만, 초라한 생각과 엉터리 철학을 부끄럽게 여길 줄 알아야 한다.” – Albert Einstein

00110101
data structure

– list와 multiset의 차이

(list 1 2 3 2) != (list 2 1 3 2)

(multiset 1 2 2 3) == (multiset 1 3 2 2)

– stl의 erase와 remove의 차이

erase / 해당하는 첫 번째 요소만 제거하며 capacity가 줄어든다.

remove / 일치하는 모든 요소를 삭제하며 capacity는 줄어들지 않는다.

– vector를 쓰는데 중간에 어떤것을 삭제하면서 배열 밀림 현상을 방지하려면?

stl에서 std::remove(itr f, itr s, t n) 알고리즘으로 삭제하였을 경우 발생.

vector.erase(std::remove(itr f, itr s, t n), vector.end())를 조합하여 사용하면 된다.

– cpp 컨테이너

스택 : LIFO 방식으로 처리 된다. 임의접근이 안된다. 마지막 위치에서의 삽입 삭제가 빠르다. 오브젝트 풀.

큐 : FIFO 방식으로 처리 된다. 임의접근이 안된다. 마지막 위치로의 삽입 처음위치의 삭제가 빠르다. 로그인 순차 예약.

덱 : 앞뒤로 삽입삭제가 가능한 큐

원형큐 : 꼬리와 헤드가 연결된 큐

트리 : 노드가 나무의 가지와 잎처럼 구성된 계층 구조. 파일 시스템. 스킬 트리.

셋 : 트리구조를 사용하는 정렬된 키값. 중복을 허용하지 않음.

맵 : 키와 밸류 두개의 쌍으로 이루어진 컨테이너. 맵이랑 셋은 정렬된 상태로 자료를 저장하고 싶을때 사용

해시맵 : 키값을 해시함수로 사용하는 맵. 해시맵은 해시테이블을 사용하여 많은 자료에서도 검색이 일정하게 빠르다. 키값 변환시 오버헤드가 있다.

리스트 : 노드들이 선형으로 연결된 리스트, 위치를 알고 있으면 삽입과 삭제가 빠르다.

벡터 : 배열처럼 연속된 메모리를 사용하는 컨테이너. 임의접근이 가능하다.

– cpp container

vector<T> // 임의접근 O(1), 끝에 추가, 삭제 O(1), 중간에 추가, 삭제 O(n)

array<T, 5> // 교환 O(n)

deque<T> // 양방향 / 임의접근 O(1), 앞이나 끝에 추가, 삭제 O(1), 중간에 추가, 삭제 O(n)

forward_list<T> // 단방향

list<T> // 양방향

priority_queue<T>

queue<T>

stack<T>

map<T, T> // 트리 기반 / 검색, 추가, 삭제 O(logn)

multimap<T, T> // 트리 기반 / 검색, 추가, 삭제 O(logn)

set<T> // 트리 기반 / 검색, 추가, 삭제 O(logn)

multiset<T> // 트리 기반 / 검색, 추가, 삭제 O(logn)

unordered_map<T, T> // 해쉬 기반

unordered_multimap<T, T> // 해쉬 기반

unordered_set<T> // 해쉬 기반

unordered_multiset<T> // 해쉬 기반

hash_map<T, T> / obsolete use <unordered_map>

hash_multimap<T, T> / obsolete use <unordered_multimap>

hash_set<T> / obsolete use <unordered_set>

hash_multiset<T> / obsolete use <unordered_multiset>

– c# collection

System.Collections

ArrayList

BitArray

Hashtable

Queue

SortedList

Stack

System.Collections.Generic

Dictionary<TKey, TValue> // unordered_map

Hashset<T> // unordered_set

LinkedList<T> // list

List<T> // vector

Stack<T> // stack

Queue<T> // queue

SortedDictionaty<TKey, TValue> // map

SortedList<T> // multiset


자료구조 개략적 전체 목록

data types

primitive types

boolean

character

floating-point

double

integer

enumerated type

composite types

array

struct

union

abstruct data types

container

list

associative array

multimap

set

multiset

stack

queue

double-ended queue

priority queue

tree

graph

linear data structures

arrays

array

bit field

bitmap

circular buffer

image

dynamic array

heightmap

lookup table

matrix

sorted array

sparse matrix

list

doubly linked list

linked list

trees

binary trees

avl tree

binary search tree

binary tree

red-black tree

self-balancing binary search tree

b-trees

b-tree

2-3 tree

2-3-4 tree

heaps

heap

binary heap

trees

trie

radix tree

space-partitioning trees

quadtree

octree

bsp tree

hashes

bloom filter

hash table

graphs

graph

adjacency list

adjacency matrix

directed graph

order

lightmap


types

container, collection

container란 object의 집합을 표현하는 data structure, abstruct data type 또는 class의 총칭이며 collection이라고도 한다. 잘 알려진 것으로는 array, list, stack, queue, table, associative array, set, tree, graph등이 있다.

container class는 보통 다음과 같은 동작을 구현한다.

빈 container 생성

저장하고 있는 요소의 수를 반환

모든 요소 제거

새로운 요소 추가

특정 요소 제거

저장하고 있는 요소의 접근

container의 요소는 어떠한 data type도 가능하며, 다른 container를 요소로 사용 할 수 있다.

container의 크기는 요소 수에 따라 자동으로 변한다. (동적 한정, 단순 array는 직접 재할당 해야됨)

abstract

abstruct data type(ADT)은 data structure와 data 연산을 정의하는 것이다. adt는 구현 방법을 정의하지 않기 때문에 data structure와는 다르다. 이는 data에 한 개념을 나타내기 위한 것으로 세부적인 스펙이나 구현등은 정의하지 않는다. 이를 정의하게 되면 abstruct data structure가 된다.

associative array(ADT)

associative array, map, symbol table 또는 dictionary는(key, value) pair collection으로 구성된 abstruct data type으로 key는 collection 안에서 하나만 존재한다. associative array는 index 이외의 data type도 key로 사용할 수 있는 배열이다. associative list, associative container, dictionary, hash, map 이라고도 부른다.

기본 동작

add or insert – collection에 새 pair 추가.

remove or delete – collectin에 있는 pair를 제거.

reassign – 기존의 존재하는 pair의 value를 수정.

lookup – 특정 key에 연관된 value 검색.

multimap(ADT)

multimap또는 multihash는 key와 연결된 abstruct data type value가 하나 이상(key 중복 효과) 있어며 반환 가능한 일반화된 map 또는 associative array 를 말한다. map과 multimap은 특수한 경우의 container이며 multimap은 map에 value로 list나 set을 넣어서 구현하기도 한다. cpp stl에서 제공하는 multimap container는 self balancing binary search tree를 사용한 정렬 multimap이다. c#에서는 multimap이 없으므로 cpp 그것과 동일한 동작을 하는 container를 만드려면 SortedDictionary와 list를 사용하여 구현한다.

list(ADT)

list는 하나 이상의 같은 value가 존재 할 수 있는 abstract data type이며 sequence라고도 한다. list는 보통 array나 linked list로 구현한다. 순서를 강조 하는 경우 sequence라고 부르게 되며 linked list와 구별한다.

기본 동작

빈 list 생성

list가 비어있는지 확인

list 맨앞쪽에 요소 추가

list 맨뒤쪽에 요소 추가

첫 번째 요소(head) 얻기

head를 제외한 부분 목록(tail) 얻기

stack(ADT)

stack또는 LIFO는 collection에 요소를 추가하는 push와 마지막으로 추가된 요소를 제거하는 pop 기본 두 동작을 가지는 요소들의 collection인 abstruct data type을 말한다. array나 linked list로 구현한다. stack은 기본 data structure의 하나로 data를 LIFO 구조로 유지한다. 콜 스택이나 오브젝트 풀등에 사용한다.

기본동작

top(peek) : 스택의 가장 윗 데이터를 넘겨준다. 만약에 비었다면 이 연산은 정의불가 상태다.

pop : 스택의 가장 윗 데이터의 값을 넘겨주고 해당 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.

push : 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, x데이터를 넣는다.

empty : 스택이 비었다면 참을 주고, 그렇지 않다면 거짓이 된다.

queue(ADT)

queue는 abstruct data type의 하나로 먼저 들어간 data가 먼저 나오는 FIFO 구조로 저장하는 형식을 말한다. 데이터를 넣는 것을 enqueue라고 하며 꺼내는 것을 dequeue라고 한다. 프린터 출력 순서나 윈도우 메시지 핸들링, 물건을 사기위해 늘어선 사람들을 생각하면 된다. linear structure로 구현된 queue의 경우 dequeue를 하고 남은 빈 공간을 사용하려면 자료 전체를 옮기거나 해야하는 단점이 있다. 이를 보완하기 위해 끝에 도달한 경우 앞쪽에 data를 보내 원형으로 구현하기도 한다. linked list로 구현하면 queue의 길이를 쉽게 늘릴 수 있어 위에서 말한 overflow가 발생하지 않는다.

double-ended queue(ADT)

double-ended queue, dequeue, deque(deck으로 발음)은 queue를 일반화한 abstruct data type으로 요소를 앞(머리)이나 뒤(꼬리)에 추가, 삭제가 가능 하다. 이때문에 head-tail linked list라고도 부른다. queue에서 data를 꺼내는 dequeue와 이름이 같기때문에 용어 사용시 주의해야 된다.

priority queue(ADT)

priority queue는 일반 queue나 stack과 비슷한 축약 자료형이다. 요소들은 우선 순위를 갖고 있으며 우선 순위가 높은 요소부터 처리 된다. 보통 heap 으로 많이 구현하며 hashtable과 같은 associative array로도 구현 할 수 있다.

기본 동작

우선 순위를 지정해서 queue에 요소를 추가한다.

가장 순위가 높은 요소를 queue에서 꺼낸다.

(추가)가장 순위가 높은 요소에 접근한다.

(추가)요소를 제거하지 않고 우선 순위를 변경한다.

set(ADT)

set은 abstruct data type의 하나로 순서가 없는 data 집합을 말하며 data 중복이 되지 않는 것을 보증한다. set은 static(frozen set)과 dynamic(mutable set)으로 나누며 이름대로 static은 생성 뒤 collection이 변경되지 않고 dynamic은 다른 collection과 같이 추가 삭제가 가능하다. cpp에서는 동일한 이름인 set을 사용 할 수 있으며 자동으로 정렬된다. c#에서는 hashset 사용 할 수 있다. set은 순서가 중요하지 않다. {1, 2, 3}과{ 3, 1, 2 }, { 2, 3, 1 }은 모두 같은 set으로 여겨진다. (cpp set, unordered_set인 경우, c# hash_set은 구별함) map과 마찬가지로 self balancing binary search tree로 보통 구현한다.

multiset(ADT)

bag이라고도 부르며 set과 다르게 중복 data를 갖을 수 있다. 각각의 동일 value들을 개별적으로 여기고 단순히 갯수를 세거나, 동일 value를 동일하게 여기고 구별된 요소로 저장한다는 두 가지 구별된 개념을 사용한다. 예로 사람들 목록(이름과 나이)이 있을 경우, 하나는 해당 나이의 갯수만 저장하는 것과 나이가 같을 경우 동일인(이름이 다르다면 다른 사람으로 판단)으로 판단하는 것이다.

arrays

정해진 크기의 동일 타입 묶음, 첨자로 접근이 가능하여 임의 접근이 가능하고 memory에 연속적으로 배치되기 때문에 O(1)의 시간복잡도를 갖는다. array는 index와 이와 대응하는 data로 이루어진 data structure이다. 일반적으로 같은 종류의 data를 순차적으로 저장하며 data의 index가 array의 시작점과 해당 data간의 상대적 위치를 나타낸다. 대부분의 프로그래밍 언어에서 사용 할 수 있는 가장 기초적인 data structure이다.

dynamic array(검색 O(1), 삽입, 삭제 O(n))

컴퓨터 공학에서 dynamic array, growable array, resizable array, dynamic table, mutable array, 또는 array list는 임의 접근및 크기가 고정적이지 않아 요소 추가 삭제가 가능한 array를 의미한다. 많은 현대 주류 프로그래밍 언어에서 기본 라이브러리로 지원한다. cpp vector가 대표적으로 array가 생성되면 일정량의 memory를 미리 잡아놓고 사용을 하다가 array 크기가 커지면 전체 크기와 함께 예약량도 늘린다. c#의 array list와 list<t>가 여기에 해당한다.

hash table(검색 O(1) – O(n), 삽입, 삭제 O(1) – O(n))

hash table또는 hash map은 key와 value를 연결 할 수 있는 구조로 associative array에 사용되는 data structure이다. hash function을 이용해서 hash를 만들고 이를 bucket(slot) array의 index로 사용한다. 이로인해 평균 검색 시간이 O(1)이다. hash function을 어떤 것을 사용하느냐에 따라서 최악의 경우 O(n)이 될 수 있다. hash 생성시 동일한 hash가 나올 가능성이 있으며 이를 collision이라고 부른다. 이를 해결하기 위해 burket을 list로 만들거나 다음 번지에 저장을 하는 식으로 문제를 해결한다.

– hash?

가변사이즈의 데이터를 고정된 길이로 변환한 값. 같은 값으로 해쉬변환을 하면 같은 값이 나온다. 하지만 해쉬충돌이라고 하여 다른값인데 같은 값이 나올 수 도 있다. 해쉬테이블, 암호화, 유사 중복 검색 등.. SHA-256bit(32byte) 알고리즘.

linked

linked data structure는 link나 pointer로 서로 reference 연결된 node들의 집합을 말한다. data간의 연결 부분을 connector라고도 부른다.

linked list(검색 O(n), 삽입, 삭제 O(1))

linked list는 각 node가 data와 pointer를 갖고 있으며 한 줄로 연결되어 있는 data structure를 말한다. 연결이 한쪽으로만 되어 있는 경우와 양쪽으로 되어 있는 경우, 원형을 되어 있는 경우가 있다. pointer로 연결 되어 있기 때문에 중간에 삽입, 삭제가 빠른 장점을 갖지만, 특정 node를 찾기 위해서는 최악의 경우 collection 전체를 돌아야 하는 단점이 있다.

doubly linked list

컴퓨터 공학에서 doubly linked list는 node라고 부르는 순차로 연결된 집합으로 구성된 연결형 data structure를 말한다. 각 node는 link라고 부르는 두 field를 갖고 있으며 이것으로 node 순차에서 이전과 다음 node를 참조 할 수 있다. 처음과 끝 node의 이전과 다음 link는 각각 list를 접근하는데 용이 하게 보통 sentinel node나 null인 일종의 종료자를 지정한다.

trees

tree는 graph의 일종으로 여러 node가 한 node를 가리킬 수 없는 구조이다. 서로 다른 두 node를 잇는 길이 하나인 graph를 tree라고 한다. 최상위 node를 root라고 하며 a가 b를 가리킬 때 a는 parent, b는 child라고 하며 child가 없는 경우 leaf라고 하고 leaf가 아닌 경우 internal이라고 한다.

binary tree

컴퓨터 과학에서 binary tree는 data structure의 하나이다. child가 둘 이하인 tree를 말한다. 보통 child는 각각 left, right node라고 부른다. binary search tree나 binary heap을 구현 할 때 사용한다.

b-tree(검색 O(logn), 삽입, 삭제 O(logn))

b-tree는 database와 filesystem에서 널리 사용되는 tree data structure로 binary tree를 확장해 child node를 둘을 초과해서 가질 수 있는 tree이다. 방대한 양의 data를 검색할 경우 앞에서 부터 비교하는 것은 상당히 비효율적이다. b-tree는 data를 정렬된 상태로 저장하며 삽입, 삭제를 O(logn)으로 할 수 있다. 보통 binary tree는 하향식인 반면 b-tree는 상향식으로 구성된다.

binary search tree(검색 O(logn) – O(n), 삽입, 삭제 O(logn) – O(n))

binary search tree(BST)는 다음의 속성을 갖는 binary tree data structure이다.

각 node에 value가 있다.

각 node의 key는 모두 달라야 한다.

value는 total order가 있다. (left child value ≤ parent ≤ right child value)

node 왼쪽 트리에는 그 node보다 작은 value를 가진 node들로 이루어진다.

반대로 node 오른쪽 트리에는 그 node보다 크거나 같은 value를 가진 node들로 이루어진다.

좌우 sub tree는 각각 다시 binary searce tree여야 한다.

중복 node가 없어야 한다.

self-balancing binary search tree

self-balancing(또는 height-balanced) binary search tree는 삽입과 삭제가 일어나는 경우 자동으로 height(root에서 내려갈 수 있는 최대 단계)를 작게 유지하는 binary search tree이다. 이 data structure는 associative array, priority queue, set과 같은 다른 abstruct data structure을 구현하는 효율적인 structure의 하나이다.

avl tree(검색 O(logn), 삽입, 삭제 O(logn))

높이차이가 1보다 크지 않도록 균형잡히게 구성하는 트리. 삽입 삭제시 트리 균형을 맞추는 작업(rotation)이 있어 비효율적이다. avl tree는 가장 초기에 나온 self-balancing binary search tree이다. 각각의 node마다 왼쪽 오른쪽 sub tree의 height 차이에 대한 정보를 가지며 sub tree들의 height 차가 1보다 크지 않은 성질을 가진다. 삽입 삭제시 원하는 node를 찾기 위해 2개의 경로가 필요하기 때문에 red-black tree만큼 효율이 좋지 않아 자주 쓰이지는 않는다. height 차이가 1을 넘어가면 rotation을 진행하며 tree 전체를 재구성한다.

red-black tree(검색 O(logn), 삽입, 삭제 O(logn))

몇가지 규칙으로 구성된 트리.

모든 노드는 레드나 블랙의 색상을 가진다.

루트와 리프노드(자식이없다)는 블랙이다.

레드 노드의 자식은 블랙이다.블랙은 둘다 가능.

리프는 무조건 널 값.

이러한 조건들을 만족하면 루트 노드로 부터 가장 먼 경로까지의 거리가 가장 가까운 경로까지의 거리의 두배보다 항상 작다 라는 특성이 있다. 균형잡혀있어 삽입, 삭제, 검색시 최악의 경우에도 시간 복잡도가 트리의 높이에 따라 결정 되기 때문에 보통의 이진트리에 비해 효율적이다.

red-black tree는 self balancing binary search tree로 대표적으로 associative array등을 구현하는 데 쓰이는 data structure이다. red-black tree에서는 leaf node들은 비어 있고 data를 가지고 있지 않는다. red-black tree는 각 node가 red나 black인 색상 속성을 가지는 binary tree이다. 기본적인 binary tree의 특성에 추가해서 다음을 만족해야 유효한 red-black tree가 된다.

node는 red또는 black중 하나다.

root는 black이다.

모든 leaf node는 black이다.

red node의 child node 양쪽 항상 black이다.
어떤 node에서 시작되어 leaf node에 도달 하는 모든 경로에는 leaf node를 제외하면 모두 같은 수의 black node가 있다.

위 조건들을 만족하게 되면, red-black tree는 가장 중요한 특성을 나타내게 된다. root node부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 red-black tree는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우에서의 시간복잡도가 tree의 height(또는 depth)에 따라 결정되기 때문에 보통의 binary search tree에 비해 효율적이라고 할 수 있다. cpp의 map, multimap, set, multiset이 red-black tree로 구현되어 있다.

heap(검색 O(n), 삽입, 삭제 O(logn))

heap은 최댓값 및 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 complete binary tree를 기반으로 한 data structure로써 A가 B의 parent node이며 A의 key와 B의 key 사이에는 대소 관계가 성립한다는 조건을 만족한다. heap은 두가지 종류가 있으며 parent node의 key가 child node의 key보다 항상 큰 heap을 ‘max heap’, 반대의 경우를 ‘min heap’이라고 부른다. key의 대소관계는 오로지 parent node와 child node간에만 성립하며, 특히 sibling node 사이에는 대소관계가 정해지지 않는다. 각 node의 child node의 최대개수는 heap의 종류에 따라 다르지만, 대부분의 경우는 child node의 개수가 최대 2개인 binary heap을 사용한다. heap에서는 가장 높은(혹은 가장 낮은) priority를 가지는 node가 항상 root node에 오게 되는 특징이 있으며, 이를 응용하면 priority queue와 같은 ADT를 구현할 수 있다.

trie

컴퓨터 공학에서 trie(또는 digital tree, radix tree, prefix tree(접두사로 검색가능 하므로))는 정렬된 tree data structure로 dynamic set이나 key가 string인 associative array을 구현 할때 사용한다. binary search tree와 다르게 각 node에 개별 key가 저장 되는 것이 아니라 node의 위치와 key가 대응한다. 어떤 노드 아래로 있는 모든 노드는 자신에 해당되는 문자열에 공통 접두사가 있으며, root에는 빈 문자열이 있다. 모든 node가 값을 가지고 있지는 않고 leaf node나 중간 node만 해당하는 값을 갖고 있다.

radix tree

간단히 말해 메모리 사용을 최적화한 trie로 patricia tree, trie라고도 부른다. child node가 하나 밖에 없는 node를 child와 병합한 것이다. 일반 trie와 다르게 edge는 한 문자뿐만 아니라 문자열도 지정할 수 있다. 이로써 집합을 작을 경우(특히 문자열이 긴 경우)와 긴 접두사를 공유하는 경우에 더욱 효율적으로 된다.

graphs

컴퓨터 공학에서 graph는 수학의 undirected graph와 directed graph 이론을 구현한 abstruct data type이다. graph data structure는 유한(하며 변형 가능한) vertex 또는 node 또는 point의 집합과 undirected graph의 vertex들의 비정렬 pair 또는 directed graph의 정렬된 pair의 집합이 함께 구성된 것을 말한다. pair는 undirected graph에서는 edge 또는 arc 또는 line이라하며 directed graph에서는 arrow 또는 directed edge 또는 directed arc 또는 directed line이라고 한다. vertex는 graph structure의 부분이거나 integer index나 참조로 표현된 외부 요소일 수 있다. graph data structure에서 각 edge는 symbolic label 또는 숫자 속성(가격, 용량, 길이등)의 edge value와 연관이 있을 수 있다.

graph는 node들과 node간의 연결 관계를 나타내는 edge들로 구성된 abstruct data type이다. graph 이론에 의한 graph의 구현이며, 이 이론에 기반으로한 다양한 알고리즘의 기초이다.graph를 실제로 표현하기 위한 주요 data structure로 2종류의 data structure가 있다.첫째는 adjacency list라는 것으로, 각 node마다 인접한 node의 list를 유지하는 data structure이다.둘째는 adjacency matrix로 불리는 것으로, column과 row에 edge의 시작점과 종점이되는 node가 늘어선 2차원 array로 표현되며 array의 각 요소는 두 node 사이에 가장자리가 있는지 여부를 나타내는 value가 저장된다.adjacency list는 드문드문 한 graph에 적합하며, 그렇지 않은 경우는 adjacency matrix이 바람직하다.또한 매우 큰 graph에서 edge에 어떤 규칙성이있는 경우 symbolic graph라는 표현도 대안으로 있을 수 있다.graph data structure는 계층적이지 않기 때문에 각 요소가 복잡하게 얽혀있는 것 같은 data를 표현하는 데 적합하다.
예를들어, 컴퓨터 네트워크를 그래프로 표현하는 데 적합하다. 계층적 data는 binary tree와 이외 tree structure로 표현된다. 그러나 tree structure는 graph structure의 특수 사례라고 볼 수 도있다.

data structure에 댓글 닫힘 | cat > 사락사락