자료구조 면접대비 질문

Hash Table

정의

collision 해결 방식

hash function

어떤 key가 주어졌을 때 hash function으로 매핑하고, 거기에 값을 저장하는 key-value store.

메모리에 쓰는 경우, 값이 유한하기 때문에 collision이 발생한다.

• separate chaining : 해당 bucket에 linked list 추가하는 방식. 쏠릴 수 있어 worst O(n)
• open addressing : 해당 위치가 아니라 빈 공간을 사용하는 방식. 예외가 많아 어렵다.

 

hash function은 임의의 길이 data를 고정 길이 data로 매핑하는 함수.

 

 

Quick Sort

pivot 기준으로 왼쪽에는 작은 수, 오른쪽에는 큰 수 둔다. pivot은 적당한 값을 고른다.

in-memory sort라서 평균적 O(nlogn)

 

 

Array, Stack, Queue, Tree, Heap, Linked List, Graph, Set

특징

array

메모리에 연속적으로 저장됨. index를 사용해 O(1)로 접근 가능.

연속적으로 할당되기 때문에, 앞/뒤에 넣는 경우에는 새로운 위치를 찾아야 하고, 중간에 들어가는 경우는 모든 요소를 미뤄야 하므로 O(n).

 

stack

last in first out

 

queue

first in first out

 

heap

complete binary tree + parent가 child보다 항상 작음. (min heap 기준)

 

tree

graph의 일종으로, edge 개수가 vertex 개수보다 1개 적은 것. connected & acycle & undirected graph

 

linked list

각 element가 이전/이후에 오는 element를 알고 있다.

삽입/삭제에 O(1).

검색하는 데는 앞에서부터 순회해야 하므로 O(n)

memory cache를 사용하지 못하기 때문에 느리다.

 

graph

vertex, edge로 이루어진 자료구조. edge는 vertex를 잇는다.

- adjacent matrix : O(n * n), 판별에는 O(1)

- adjacent list : O(V+E), 판별에는 O(deg(v))

 

set

중복 허용 X

 

 

binary tree 종류

binary search tree

complete binary tree

balanced binary tree

perfect binary tree

binary search tree

검색 위해 사용, binary tree인데, 정렬된 것. parent보다 작은 것들이 왼쪽, 큰 것이 오른쪽에 온다.

worst case O(n)이라서, balanced binary search tree 등으로 O(logn)을 유지할 수 있다.

 

complete binary tree

마지막 level 제외하고는 모든 level이 완전히 채워짐.

- min heap의 경우 parent가 child보다 항상 작다. 삽입 시 제일 끝에 넣고 swap, 삭제 시 root로 올리고 비교하며 내림.

 

balanced binary tree

left child와 right child의 height 차이가 최대 1. avl이나 rb tree.

- avl에서 삽입/삭제 시 회전한다.

- rb tree에서 색을 사용해 균형 유지. avl보다 조금 빠르다.

 

perfect binary tree

leaf node 제외, 모두 2개의 child 가짐

 

 

Trie

정의

문자열에서 검색 빠르게 도와줌.

문자열을 tree로 만든 것.