자료구조 면접대비 질문
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로 만든 것.