[CS] CS 면접 대비 : 자료구조 3

기술면접 예상 질문 및 답변

Hash 충돌 회피 방법에 대해서 설명해주세요.

Hash 충돌 회피 방법으로, open addressing, double hashing, chaining 등이 있습니다. open addressing은 Hash 충돌이 일어났을 경우 순차적으로 비어있는 버킷을 확인해 저장하는 방법이고, double hashing은 종류가 다른 해시함수를 추가로 계산해서 해당 하는 인덱스에 저장하는 방법입니다. chaining은 버킷을 lineked list로 구성하여 충돌이 일어났을 경우 list에 추가 해주는 방법입니다.

 

chaining 회피 방법의 단점에 대해서 설명해주세요.

충돌로 인해 한 버킷에만 자료들이 리스트에 추가된다면, 최악의 경우 조회 시간복잡도가 O(n)이 됩니다.

 

PriorityQueue에 대해서 설명해주세요.

PriorityQueue는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼낼 수 있는 자료구조입니다. Heap 자료구조를 사용해 구현되어 있습니다.

 

퀵 정렬에 대해서 설명해주세요.

퀵 정렬은 분할 정복 알고리즘 중 하나로 평균 시간복잡도가 O(nlogn)입니다. 하나의 리스트를 피벗을 기준으로 작은 값과 큰 값으로 분할을 반복하고 배열의 크기가 1개 이하가 될 경우 정렬되게 합병하는 과정을 통해 정렬이 이루어집니다.

 

퀵 정렬이 최악의 경우 O(n^2)인 이유에 대해서 설명해주세요.

정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있는 경우에 편향적으로 분할하기 때문에 시간복잡도가 O(n^2)이 됩니다.

 

Merge Sort보다 Quick Sort가 빠른 이유에 대해서 설명해주세요.

Merge Sort는 분할하는 과정에서 새로운 메모리를 할당하고 해제하는 과정이 필요하기 때문에 새로운 메모리를 할당하고 해제해야 하는 오버헤드가 발생하기 때문에 Quick Sort보다 느립니다.

 

자가 균형 트리에 대해서 설명해주세요.

자가 균형 트리는 트리에서 노드의 삽입과 삭제가 이루어질 때 서브 트리의 높이 차가 1이하를 보장하는 트리입니다.

 

Binary Search Tree에 대해서 설명해주세요.

이진 탐색 트리는 이진 탐색과 연결 리스트를 결합한 자료구조입니다. 왼쪽 서브 트리의 모든 값은 부모 노드보다 작아야 하고, 오른쪽 서브 트리의 모든 값은 부모 노드보다 큰 값을 가져야 하는 특징이 있습니다.

 

탐색 시간 복잡도에 대해서 설명해주세요.

평균 시간 복잡도는 O(logn)이지만, 편향트리가 될 수 있기 때문에 최악의 경우 O(n)입니다.