자료 구조 면접 대비

Array와 LinkedList의 차이는 무엇인가요?

Array와 LinkedList는 요소가 일렬로 나열되어 있는 선형 자료 구조입니다. 차이점으로 배열은 랜덤 접근이 가능하지만 연결 리스트는 순차적 접근만 가능합니다. 따라서 랜덤 접근이 가능한 배열은 탐색에 O(1)이 소요되지만 삽입과 삭제에는 O(N)이 소요됩니다. 그리고 순차적 접근이 가능한 연결 리스트는 탐색에 O(N)이 소요되지만 삽입과 삭제에는 O(1)이 소요됩니다.

Stack과 Queue의 차이는 무엇인가요?

Stack과 Queue는 요소가 일렬로 나열되어 있는 선형 자료 구조입니다. 차이점으로 스택은 마지막으로 들어간 데이터가 먼저 나오는 LIFO 성질을 지녔지만 큐는 먼저 들어간 데이터가 먼저 나오는 FIFO 성질을 지녔습니다. 이 성질들을 이용해 스택은 주로 재귀함수, 웹 브라우저 방문 기록 등에 쓰입니다. 그리고 큐는 주로 너비 우선 탐색, CPU 작업을 기다리는 프로세스, 캐시 등에 사용됩니다. 두 자료 구조는 모두 탐색에 O(N)이 소요되지만 삽입과 삭제에는 O(1)이 소요됩니다.

PriorityQueue의 동작 원리는 어떻게 되나요?

우선순위 큐는 큐에서 우선순위가 높은 요소가 먼저 제공되는 자료 구조입니다. 이는 힙을 기반으로 구현됩니다. 이 힙에 새로운 요소가 들어오면 힙의 마지막 노드에 삽입이 되고 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킵니다. 그리고 힙에서 삭제를 할 때에는 최대힙이면 최댓값이 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성됩니다.

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

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있습니다.