[ 알고리즘 ] 자료구조 내용 복습

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다.

 

  

1. Array

동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 

갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다.

 

인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다.

ex) A[7] = 400 + 7*4 = 428 

 

Search, Delete, Insert 입장에서 효율이 좋지 않다. 

sorting이 되어있다면 Binary Search O(log N)가능하다. 

 

 

2. Stack

insertO(1) / DeleteO(1)만 제공한다. Search x

 

Last in, First out 

 

수식 계산에 사용

ex (3+7)*2 + (6-3)/5

 

3. Queue

insert O(1) / Delete O(1)만 제공한다. Search x

 

First in, First out

 

4. LinkedList

노드 (메모리에 있는 한 단위) 

 

 

node

 

포인터는 다음노드의 주소가 저장되어 있는 공간이다.

 

Search해서 Delete를 할 수 있지만 느리다

 

 

5. Binary Search Tree

search, delete, insert 가 모두 빠르다.

 

search tree는 sorting해서 저장하는 방법

왼쪽은 (전부) root보다 작고, 오른쪽은  (전부) root보다 크다.

 

노드마다 key가 있다 (일차원적으로 정렬할 수 있는 값)

각각의 서브트리도 BST이다. 

 

Binary Search Tree

 

ex) 14를 찾아라

 

->

<-

->

not found

 

값이 있다 없다 알 수 있는 것만으로 유용하다

 

재귀로 짜는 것이 가장 편하다.

 

 

6. Heap 

6.1 Heap Insert

(up heap) 가장 작은 값 확인.  간단하고 굉장히 빠르다.

 

child가 2개인데 어느 길을 따라가든 수는 커진다.

우선순위 큐를 이용한다. 제일 작은 걸 꺼내는 방식(루트엔 가장 작은 값이 위치한다.)

 

Heap Insert

새로 추가한 값은 항상 맨 끝에 들어가며 위로 올라가며 자기 자리를 찾는 방식

 

Heap Insert

 

a가 새로 추가된거라면,

a가 c보다 크면 그 자리에 있으면 되고 작으면 올리면 된다.

 

이런식으로 추가하면 힙은 전체가 조건을 만족한다.

 

6.2 Heap Delete

(down heap)

Heap Delete

삭제하면 맨위 자리가 빈다. 맨 밑을 맨 위로 올린다.

자식노드 양쪽을 비교해서 아래쪽이 루트보다 더 작다면

더 작은 애를 위로 올린다.

모든 노드의 크기관게를 다 맞추기 위해 반복해서 따라 내려간다.

 

노드가 N개 있다면 O(log N)

 

7. AVL Tree

BST가 보통의 경우에 성능이 좋지만, 특수한 경우에 안 좋다. = > Balanced Tree 최악의 경우에도 O(logN)

 

AVL Tree

 

왼쪽, 오른쪽 subtree의 높이 차이가 1이하

 

루트에서 갈 수 있는 제일 짧은 길과 제일 긴 길 차이가 2배 이하다.

중간까지는 tree높이에 비해서 노드 수가 많기 떄문에

=> 노드 갯수에 비해서 tree 높이가 작다. => O(log n)

 

 

 

8. 2-3 Tree

key가 2개 있고 child가 3개 있는 노드를 섞어서 만든다.

AVL tree와 비슷하다

 

2-3 Tree

 

삽입할땐 key와 key사이 가운데로 삽입되어서 위로 올라갈 수 있으면 올라간다. 

 

 

9. Graph

 

G = (V,E)

V : 노드 set - any set(finite)

E : 엣지 set 

 

가능한 edge는 nC2개 = n(n-1)/2

 

그래프를 컴퓨터 안에 어떻게 표현할 것인가?

 

1. 인접그래프 - edge많을 때

메모리 많이 쓰지만 빨리 찾을 수 있음 (노드^2)

(무방향 그래프이므로 대칭)

 

2. 인접 리스트 - edge적을 때 (보통 이거 씀)