내가 하고싶은 것!/취준

자료구조 면접대비 질문

hyelie 2023. 10. 4. 10:05

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로 만든 것.