위 도서를 읽고 정리하여 기술 면접에 대비하는 글입니다.
5.1 복잡도
5.1.1 시간 복잡도
5.1.2 공간 복잡도
5.1.3 자료 구조에서의 시간 복잡도
5.2 선형 자료 구조
5.2.1 연결 리스트
5.2.2 배열
5.2.3 벡터
5.2.4 스택
5.2.5 큐
5.3 비선형 자료 구조
5.3.1 그래프
5.3.2 트리
5.3.3 힙
5.3.4 우선순위 큐
5.3.5 맵
5.3.6 셋
5.3.7 해시 테이블새롭게 알게 된 점
스택과 큐의 예시
- 스택: 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록
- 큐: CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용
이진 탐색 트리
노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리.
AVL 트리
Adelson-Velsky and Landis trees는 이진 탐색 트리 삽입 순서가 최악의 경우가 되어 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리.
두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.
레드 블랙 트리
균형 이진 탐색 트리.
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용
헷갈리는 점
자료 구조에서의 시간 복잡도
- 자료 구조의 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(N) | O(N) | O(N) |
| 스택(stack) | O(N) | O(N) | O(1) | O(1) |
| 큐(queue) | O(N) | O(N) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(N) | O(N) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logN) | O(logN) | O(logN) | O(logN) |
| AVL 트리 | O(logN) | O(logN) | O(logN) | O(logN) |
| 레드 블랙 트리 | O(logN) | O(logN) | O(logN) | O(logN) |
- 자료 구조의 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(N) | O(N) | O(N) |
| 스택(stack) | O(N) | O(N) | O(1) | O(1) |
| 큐(queue) | O(N) | O(N) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(N) | O(N) | O(N) | O(N) |
| 해시 테이블(hash table) | O(N) | O(N) | O(N) | O(N) |
| 이진 탐색 트리(BST) | O(logN) | O(logN) | O(logN) | O(logN) |
| AVL 트리 | O(logN) | O(logN) | O(logN) | O(logN) |
| 레드 블랙 트리 | O(logN) | O(logN) | O(logN) | O(logN) |
느낀 점
생각보다 내가 자료 구조에 대해 아는 것이 많고,
이걸 이제 면접 답변에 조리 있게, 그리고 썼던 경험들을 덧붙여서 정리할 필요성을 느꼈다.
프론트엔드 기술 학습 및 공유를 활발하게 하기 위해 노력합니다.