'학부 전공/자료구조' 카테고리의 글 목록

* Hash Table

- 최악의 경우를 따지지 않고, 평균적인 경우 즉 대부분의 경우에만 가능한 자료구조

- 조건에 맞으면 동작이 상수 시간 안에 끝나고, 간단하다.

- delete가 복잡하다. delete가 많은 상황에서는 쓰지 않는다.

- idea : 지정석. ex) 100만개의 가능한 키가 모두 등장.

- 정의 : 키 값 k, k->h(k)

h(k) : Hash Function. 범위는 0부터 배열의 크기-1 까지.

- k는 h(k)에 저장한다.

- Hash function. (입력값과 무관해 보이는 결과값을 원함)

k % n

(p*k) % n

string folding

-Overflow handling (거의 발생하지 않는다. 따라서 성능에 특별한 영향을 안 줌)

Open Addressing : linear probing(+1, +2 ...), quadratic probing(^2, ^3 ....) , rehashing(다른 hash함수 사용)

, random probing( pseude random number generator 사용)

Chaining : 해당 인덱스를 링크드 리스트로 만들어서 저장

Overflow bucket : 특정 공간을 만들어서 overflow된 값들을 저장. 디스크에서 주로 사용.

Dynamic Hashing : 넘치면 두배로 늘림. 늘린후 hash값을 모두 재계산 하거나 lazy separation을 사용

Bloom Filter : hash table보다 훨씬 큰 bitmap filter를 사용. table에 없는 값을 search할 경우 filter에서 걸러짐. 실제로 많이 사용됨.

* RADIX

-내부 구조에 관심을 가져보자

-많은 경우에 O(nlog n). 범위가 좁고 개수가 적당할수록 성능이 보장됨

- Compression : Run-Length Encoding, Differential Encoding, Huffman Encoding

Huffman Encoding

- idea : 자주 등장하는 character를 짧은 bit sequence로 표현.

- 각 character의 등장 확률이 미리 주어졌을 때, 최적의 prefix-tree code 생성

- radix의 한 예. tree의 좌, 우가 의미하는 바가 key의 내용에 관계가 있음.

- counting sort : 배열의 데이터가 곧 해당하는 인텍스 넘버의 개수.

- bucket sort : 배열에 버켓을 범위별로 나눠서 넣은 후 각각을 sort.

- radix sort : 배열에 버켓을 2개만 놓고 1개는 첫비트가 0인것, 나머지 1개는 1인것으로 넣음. 그리고 반복.

* Binary Trie

- retrieve, 꺼내기 쉬운 자료구조

- 키 : integer ( 2진수로 표현 )

- 왼쪽 child는 해당 비트가 0 인 것, 오른쪽 child는 해당 비트가 1인 것.

- Compressed Binary Trie : 특정 노드 이하로 하나의 leaf만 존재할 경우, 그 leaf까지의 모든 비트를 한 레이블에 모아서 적어놓음. delete가 복잡해짐

- Radix trie, Patricia : compressed binary trie의 변형. interner node를 없앰.

- string trie : child로 가는 edge가 해당 칸의 문자열을 의미.

- Aho-corasick Trie : multiple keyword matching.

- Suffix tree : index structure. compressed trie 기반. 사전에 사용.

'학부 전공 > 자료구조' 카테고리의 다른 글

10. 탐색구조 (0)	2010.06.15
5. Tree (0)	2010.06.08
4. Linked List (0)	2010.06.07
3. Stack / Queue (0)	2010.06.07
2. 배열 (0)	2010.06.07

- 최악의 경우에도 insert, search, delete가 O(log n)을 유지

10.2 AVL tree

- 정의 : Binary tree + label

- 각각의 node에 left, right label 표기

-left label : 왼쪽 subtree의 depth

-right label : 오른쪽 subtree의 depth

- left label과 right label이 2 이상 차이가 안 나게 유지.

(항상 같거나 1 차이.)

-Search : binary search tree와 동일. O(log n)

-Insert : binary search tree Insert + Tree 보정 ( label 조건을 만족시키기 위함)

-일단 insert를 시키고 난 후, search한 PATH를 따라 올라가다가 최초로 조건을 만족시키지 않는 node에서 Rotation.

*Rotation

-LL, LR, RL, RR

-LL의 경우: 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child를 올림.

left child의 right child는 원래 root node의 left child로 바꿈.

RR의 경우 좌우 대칭

-LR의 경우 : 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child의 right child를 올림.

root로 올린 node의 left child는 원래 자리의 parent에 붙이고, right child는 원래의 root node에 붙임.

- Rotiation을 진행 하더라도 기본적인 크기 관계가 변하면 안 됨.

10.3 2-3 tree

- 정의 : 각 node에 키가 1개 혹은 2개, 따라서 각 node의 child가 2개 혹은 3개. 모든 leaf는 같은 level.

- search : O(log n)

- insert : search를 한 후에, leaf에 빈자리가 있으면 그냥 insert, 빈자리가 없으면 leaf를 split해서 중간값을 parent로 올려보내고 반복.

10.4 2-3-4 tree

- 각 node에 키가 1개 혹은 2개 혹은 3개.

- 나머지는 2-3 tree와 같으나 insert를 할 때, split을 하면서 내려오게 할 수 있다.-> tree를 한번 내려오면 insert가 끝남.

10.5 Red-Black tree

- 2-3-4 tree의 변형

- 2-3-4 tree를 binary tree형태로 표현.

- child node로 가는 link를 black으로, 같은 node에 있는 키로 가는 link를 red로 표시.

-특징 : root에서 leaf까지 black link의 수는 항상 동일, 어떤 path에서도 red link가 연속으로 등장하지 않는다.

-insert 과정은 AVL tree의 Rotation과 같다.

- AVL, 2-3, 2-3-4, Red-Black tree를 통틀어 Balanced tree라 부른다.

* Skip list

- head와 tail이 더미 노드인 링크드 리스트가 층으로 쌓여있는 자료구조

- 모든 동작이 O(log n)에 된다.

'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie (0)	2010.06.15
5. Tree (0)	2010.06.08
4. Linked List (0)	2010.06.07
3. Stack / Queue (0)	2010.06.07
2. 배열 (0)	2010.06.07

-그래프의 특수한 경우

- Connected Graph with no cycle

*정의

1. 하나 이상의 노드로 이루어진 자료구조

2. 노드들 중 하나는 root이다.

3. root를 제외한 나머지 노드들은 subtree들로 분할된다.

4. root와 subtree의 root 사이에는 edge가 있다.

*용어

- node의 subtree root를 node의 child라고 부른다.

- degree(차수) : node의 child 수

- degree가 0인 node : leaf, terminal

- A가 B의 child => B는 A의 parent

- parent가 같은 node들 => 형제(sibling)

- root level : 1, node level : parent level + 1, 제일 큰 level : heght or depth

- parent, parent의 parent, ,,,,,, => 조상(ancestor)

- child, child의 child, ...... => 자손(descendant)

5.1.1 Tree의 표현(child를 표현하는 방법)

1) 배열 방법

2) Left child - Right sibling

3) Binary Search Tree

5.2 Binary Tree

- child가 최대 2개인 tree

5.2.3 Binary tree의 표현

- 배열에 embeded.

- 배열의 i에 있는 node의 children은 2i, 2i+1에 존재

5.3 Tree Traversal

-정의 : root에서 시작해서 node들을 "지정된 순서"에 따라서 "방문"하는 것

-종류 : preorder, inorder, postorder

-트리에 다항식을 넣으면 전위/중위/후위 연산자 표현이 가능하고, 변수를 넣으면 기계어를 만들 수 있다.

5.6 Heap

- 우선 순위 큐를 만들 때 사용

- Complete Binary Tree.

- 어떤 노드의 키 값은 children의 키 값보다 작다.

- Heap Insert : up-heap. leaf중에서 제일 오른쪽에 추가한 후, parent와 비교해서 조건에 안 맞으면 교환. 그리고 반복

- Heap Delete : down-heap. root를 보내주고, leaf중에서 제일 오른쪽에 있는 것을 root로 올린 후, children과 비교해서 조건에 안 맞으면 교환. 그리고 반복.

- tree는 재귀적으로 코딩하면 더 쉬워진다.

5.7 Binary Search Tree

- Binary tree

- left, right의 children

- node a의 left subtree : a의 키보다 작은 키 값

- node a의 right subtree : a의 키보다 큰 키 값

- Insert : Search를 한 후, 실패했다면 그곳에 새 child로 insert

- Delete : leaf일 때는 그냥 삭제, one child 일때는 child를 parent에 붙여주고 삭제, two children 일때는 오른쪽으로 한번, 왼쪽으로 계속 내려가서 만나는 leaf랑 해당 노드를 바꾼 후, 바뀐 leaf를 삭제.

5.10 Union-Find

-집합의 연산 중 합집합과 대표 원소 찾기(집합 이름 찾기, 두 원소가 같은 집합에 있는지 확인)

-Minimum Spanning Tree 문제

-연결을 유지하면서 최소 비용 쓰기

방법1 : 한 노드르 찍고, 최소 비용 edge를 추가 해나감.

방법2 : 전체 edge를 sorting한 다음, 최소 비용 edge부터 추가 해나감

-항상 사이클을 만들지 않는다.

-사이클 검사 : 방법1 일때는 Tree에 이미 포함된 노드 둘을 연결할 때 사이클이 생기고, 방법2 일때는 같은 덩어리에 있는 노드 둘을 연결할 때 사이클이 생김.

-구현 : 배열상에서 구현. 포인터는 index, 무제한 tree, 포인터 방향은 child->parent. 즉 해당 node는 자신의 parent의 index의 값을 가지고 있음.

- 성능 : Find와 Union 둘 다 tree depth에 비례.

- Path Compression 사용

'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie (0)	2010.06.15
10. 탐색구조 (0)	2010.06.15
4. Linked List (0)	2010.06.07
3. Stack / Queue (0)	2010.06.07
2. 배열 (0)	2010.06.07

-Linked List의 특징 : 순서를 유지한다. 삽입과 삭제를 주로 한다. Binary Search가 불가능 하다.

-Node와 Link로 구성되어 있다.

-Node는 데이터를 저장하는 Linked List의 구성단위이고, Link는 Node와 Node를 연결하는 포인터이다.

-Multi thread에서는 포인터 하나로 delete를 수행할 수 없다.

-메모리 사용이 유연한 장점이 있다.

*다항식

-다항식 표현에 다양하게 사용된다.

*동치관계(등호의 예)

1) Reflexive : 모든 a에 대해서 a = a이다.

2) Symmetric : 모든 a,b에 대해서 a = b이면 b = a이다.

3) Transitive : 모든 a,b,c에 대해서 a = b, b = c이면 a = c이다.

-동치관계의 일부가 주어졌을 때, 주어진 것으로 유추할 수 있는 자연스러운 partition을 계산하는데 쓰인다.

-DFS(depth first search : 깊이 우선 탐색)

'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie (0)	2010.06.15
10. 탐색구조 (0)	2010.06.15
5. Tree (0)	2010.06.08
3. Stack / Queue (0)	2010.06.07
2. 배열 (0)	2010.06.07

- Search를 고려하지 않음

- Insert와 Delete 대신에 Push와 Pop을 씀.

- 값에 의존하지 않고 순서에만 의존.

*Stack : Last-in First-out 방식(LIFO)

*Queue : First-in First-out 방식(FIFO)

-Queue에서는 full 과 Empty 일 때 top,bottom포인터의 상대위치가 같기 때문에 구별해주어야 한다.

*미로찾기

-길을 찾다가 막혀있으면 왔던 길을 되돌아 간다. 왔던 길의 좌표를 Stack에 저장해 놓을 수 있다.

*수식의 계산

-infix(중위표기법) : 연산자를 연산하려는 두 숫자 사이에 두는 방법. 예) 3 + 5

-postfix(후위표기법) : 연산자를 연산하려는 두 숫자 뒤에 두는 방법. 예) 35+

-prefix(전위표기법) : 연산자를 연산하려는 두 숫자 앞에 두는 방법. 예) +35

이 중에서 인간이 이해하기 쉬운 표현은 infix, 프로그램 입장에서 이해하기 쉬운 표현은 postfix.

*infix를 postfix로 변환하는 알고리즘

1. 피연산자인 경우 출력

2. 연산자인 경우 Stack top의 연산자와 우선순위를 비교하여 입력된 연산자의 우선순위가 더 높을 경우 Push하고, Stack top의 연산자의 우선순위가 더 높을 경우 Pop한 후 반복 비교.

*postfix로 된 수식을 계산하는 알고리즘

1. 피연산자이면 Stack에 Push

2. 연산자이면 Stack에서 피연산자 2개를 Pop해서 계산 한 후, 결과는 Push

-최하위 우선순위를 가지는 연산자를 하나 지정해서 Stack에 미리 넣어두면, 코드가 단순해진다.

'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie (0)	2010.06.15
10. 탐색구조 (0)	2010.06.15
5. Tree (0)	2010.06.08
4. Linked List (0)	2010.06.07
2. 배열 (0)	2010.06.07

* 자료구조의 operation

- insert

- search

- delete

-배열의 정의 : 연속된 주소에 "같은 type"의 data item에 저장되는 자료구조.

-배열의 (유일한) 장점 : K번째 item을 상수 시간에 접근 가능.

-배열의 단점 : 크기변경이 어렵다.

-배열의 4가지 사용방법

1. Packed Sorted

2. Unpacked Sorted

3. Packed Unsorted

4. Unpacked Unsorted

-용도에 따라 4가지를 구별해서 쓴다. 각각 operation 성능이 조금씩 다르다.

- Binary search의 성능 : O(log n)

'학부 전공 > 자료구조' 카테고리의 다른 글

Hash Table, Radix, Binary Trie (0)	2010.06.15
10. 탐색구조 (0)	2010.06.15
5. Tree (0)	2010.06.08
4. Linked List (0)	2010.06.07
3. Stack / Queue (0)	2010.06.07

정리 불가능의 영역