[5] 자료 구조
면접을 위한 CS 전공지식 노트 CHAPTER 5
SECTION 5.1 복잡도
5.1.1 시간 복잡도
빅오 표기법
- ‘얼마나 오랜 시간’이 걸리는지를 나타냄
- ‘가장 영향을 많이 끼치는’ 항의 상수 인자를 빼고 나머지 항을 없앤 것
5.1.2 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
- 정적 변수 + 동적 재귀 함수 공간
SECTION 5.2 선형 자료 구조
5.2.1 연결 리스트
- 공간 효율성을 극대화시킨 자료 구조
- 삽입•삭제: O(1) / 탐색: O(n)
- 랜덤 접근 불가능
- 싱글 연결 리스트: next 포인터만 가짐
- 이중 연결 리스트: next 포인터와 prev 포인터를 가짐
- 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것
5.2.2 배열
- 중복 허용, 순서 있음
- 삽입•삭제: O(n) / 탐색: O(1)
- 랜덤 접근 가능
5.2.3 벡터
- 동적으로 요소를 할당할 수 있는 동적 배열
- 컴파일 시점에 개수를 모를 때 사용
- 맨 뒤나 맨 앞 삽입•삭제: O(1) / 나머지 삽입•삭제: O(n)
- 의 제곱승 + 1 마다 크기를 2배로 늘림
함수
- push_back()
- pop_back()
- erase()
- find()
- clear()
5.2.4 스택
- LIFO(후입선출)
- 삽입•삭제: O(1) / 탐색: O(n)
함수
- push()
- pop()
5.2.5 큐
- FIFO(선입선출)
- 삽입•삭제: O(1) / 탐색: O(n)
- 프로세스, 스레드 행렬, 네트워크 접속을 기다리는 행렬, BFS, 캐시
함수
- enqueue()
- dequeue()
SECTION 5.3 비선형 자료 구조
5.3.1 그래프
정점 + 간선
정점과 간선
- 정점: vertex
- 간선: edge
-
가중치: 간선과 정점 사이에 드는 비용
- 나가는 간선: outdegree
- 들어오는 간선: indegree
5.3.2 트리
그래프 → 계층적
루트 노드, 내부 노드, 리프 노드
특징
1. 부모, 자식 계층 구조
2. V - 1 = E
3. 어느 노드와의 경로는 반드시 있어야 함
노드
- 루트 노드: 가장 위에 있는 노드
- 내부 노드: 루트 노드와 내부 노드 사이에 있는 노드
- 리프 노드: 자식이 없는 노드
높이와 레벨
- 깊이: 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
- 높이: 가장 긴 거리
- 레벨: 깊이
- 서브트리: 하위 집합
이진 트리
자식의 노드 수가 두 개 이하인 트리
- 완전 이진 트리: 왼쪽부터 채워져 있는 이진 트리
이진 탐색 트리
- BST
- 왼쪽: 노드 값보다 작은 값
- 오른쪽: 노드 값보다 큰 값
AVL 트리
- 스스로 균형을 잡는 이진 탐색 트리
- 두 자식 서브트리의 높이는 항상 최대 1만큼 차이남
- 탐색•삽입•삭제: O(logn)
- 회전시키며 균형 잡음
레드 블랙 트리
- 균형 이진 탐색 트리
- 탐색•삽입•삭제: O(logn)
- 블랙, 레드 레벨 별로 번갈아서 나옴
- 모든 루트와 리프 노드는 블랙
5.3.3 힙
완전 이진 트리
- 최대힙: 루트 노드 값이 최댓값
- 최소힙: 루트 노드 값이 최솟값
✏️ 최대힙 삽입 과정
- 마지막 노드에 삽입
- 새로운 노드를 부모 노드들과 비교
- 힙의 성질 만족
✏️ 최대힙 삭제 과정
- 루트 노드 삭제
- 마지막 노드와 루트 노드 스왑
- 힙의 성질 만족
5.3.4 우선순위 큐
우선순위 높은 순대로 제공
5.3.5 맵
- 키+값
- 레드 블랙 트리 기반
- 삽입하면 자동 정렬
5.3.6 셋
- 중복x, 고유한 값
5.3.7 해시 테이블
- 무한한 데이터를 유한한 개수의 해시 값으로 매핑한 테이블
- 탐색•삽입•삭제: O(logn)
댓글남기기