CS 자주 나오는 질문 정리 (2)

자료구조

좋아하는 자료구조가 있다면 이유와 함께 설명해주실 수 있을까요?
- 좋아하기보다는 프로젝트를 하면서 많이 사용했던 것
- 해시테이블 : 해시 테이블은 키(Key)를 값(Value)에 매핑하여, 평균적으로 상수 시간(O(1))에 데이터를 검색, 삽입, 삭제할 수 있는 효율적인 자료구조입니다. 이는 많은 양의 데이터를 빠르게 처리해야 하는 경우에 매우 유용합니다. 또한, 해시 테이블의 유연성은 다양한 유형의 데이터를 쉽게 저장하고 관리할 수 있게 해줍니다.

스택, 큐에 대해 설명해주실 수 있을까요?
- 스택: 스택은 후입선출(Last In First Out, LIFO) 방식의 자료구조입니다. 이는 마지막에 삽입된 요소가 가장 먼저 나오는 구조를 가지고 있어, 깊이 우선 탐색(DFS) 같은 알고리즘에서 유용합니다.
- 큐: 큐는 선입선출(First In First Out, FIFO) 방식의 자료구조입니다. 이는 가장 먼저 삽입된 요소가 가장 먼저 나오는 구조로, 너비 우선 탐색(BFS) 같은 알고리즘 또는 대기열 관리에 적합합니다.
→ 스택과 큐 모두 자료구조의 개념입니다.큐란 파이프형태를 띄는 자료구조입니다. FIFO의 형태를 가지며, 가장 처음 입력된 데이터가 가장 먼저 나가게 되는 형태입니다. 사용의 예로는 입력된 데이터의 시간순서대로 처리해야 할 경우 사용합니다.
스택이란 탑처럼 쌓아올리는 형태를 가지며 LIFO의 형태로 제일 마지막에 입력된 데이터가 제일 먼저 나가게 되는 형태입니다. 사용의 대표적인 예로는 웹브라우저의 뒤로가기가 있습니다.

배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?
- 배열: 배열은 메모리에 연속적으로 데이터를 저장합니다. 이로 인해 인덱스를 통한 빠른 접근이 가능하지만, 크기 변경이 어렵고 삽입 및 삭제 연산에서 비효율적일 수 있습니다.
- 링크드 리스트: 링크드 리스트는 각 요소가 포인터를 통해 연결된 구조입니다. 배열과 달리 메모리를 비연속적으로 사용하여 크기 변경이 유연하고, 삽입 및 삭제가 용이하지만, 특정 요소에 접근하기 위해서는 순차적 탐색이 필요합니다.
→ 배열은 메모리상에 연속으로 데이터가 저장된 형태의 자료구조이며, 연속적으로 저장되어 있기때문에 인덱스를 활용하여 데이터에 접근 가능합니다.
링크드리스트는 배열과 다르게 노드라는 개념이 사용됩니다. 노드들이 순차적으로 연결되어있는 형태의 자료구조이며, 각 노드들은 저장할 데이터와 다음 노드를 가리키는 포인터를 가지게 됩니다.
배열과 달리 연속적으로 저장되어있지 않기때문에 인덱스 번호로 데이터 접근이 불가하며, 배열에 비해 데이터 삭제와 삽입에 용이합니다.

해시테이블의 원리, 충돌 해소 전략에 대해 설명해주실 수 있을까요?
- 원리: 해시 테이블은 해시 함수를 사용해 키를 해시 코드로 변환하고, 이 코드를 사용하여 값을 저장하거나 검색합니다. 해시 함수는 데이터를 효율적으로 분산시켜야 합니다.
- 충돌 해소 전략:
  - 체이닝(Chaining): 충돌이 발생하면, 같은 해시 버킷에 연결 리스트로 요소를 추가합니다.
  - 오픈 어드레싱(Open Addressing): 충돌이 발생하면, 빈 버킷을 찾을 때까지 다른 버킷으로 이동합니다. 선형 탐색, 제곱 탐색, 이중 해싱 등의 방법이 있습니다.

우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?
- 우선순위 큐는 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소부터 제거됩니다. 이는 힙(Heap)과 같은 자료구조를 사용하여 구현됩니다.
- 삽입 연산: O(log n), 우선순위에 따라 적절한 위치에 요소를 삽입하기 위해 힙을 재정렬합니다.
- 삭제 연산: O(log n), 힙의 루트(가장 높은 우선순위의 요소)를 제거하고, 힙을 재정렬합니다.
- 이러한 시간 복잡도는 힙의 특성 때문에 발생합니다. 힙은 완전 이진 트리의 형태를 취하며, 각 연산마다 트리의 높이에 비례하는 시간이 소요됩니다.