면접을 위한 CS 전공지식 노트 - 자료 구조

자료 구조란?

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합이다.

 

시간 복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계이다.

- 빅오 표기법
입력 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이다.
ex. O(n), O(logn) 등

 

공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양이다.

 

선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조이다.

1. 연결 리스트
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다.
삽입과 삭제가 O(1) 걸리며 탐색에는 O(n) 걸린다.

2. 배열
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
중복을 허용하고 순서가 있다.
탐색에 O(1)이 되어 랜덤 접근이 가능하고, 삽입과 삭제에는 O(n)이 걸린다.

3. 벡터
동적으로 요소를 할당할 수 있는 동적 배열이다.
컴파일 시점에 개수를 모른다면 벡터를 써야한다.
중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
맨 뒤의 요소를 삽입/삭제에는 O(1)이 걸리며, 그 외의 요소를 삽입/삭제에는 O(n)이 걸린다.
벡터의 크기가 증가되는 시간 복잡도는 상수 시간 복잡도 O(1)과 유사한 시간 복잡도를 갖는다.

4. 스택
가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO)을 가진 자료 구조이다.
삽입 및 삭제에 O(1), 탐색에 O(n) 걸린다.

5. 큐
먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)을 지닌 자료 구조이다.
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.

 

비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조이다.

1. 그래프
정점과 간선으로 이루어진 자료 구조이다.

2. 트리
정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.
루트 노드, 내부 노드, 리프 노트 등으로 구성된다.

* 이진 트리 : 자식의 노드 수가 두 개 이하인 트리이다.
* 이진 탐색 트리 : 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리이다.
* AVL 트리 : 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다.
* 레드 블래 트리 : 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn) 이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다.

3. 힙
완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특징을 지킨 트리이다.

* 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
* 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

4. 우선순위 큐
대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조이다.
(힙을 기반으로 구현된다.)

5. 맵
특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조이다.
(map<string, int> 형태로 구현한다. ex. "김지현": 1, "hyunn": 2)

6. 셋
특정 순서에 따라 고유한 요소를 저장하는 컨테이너이다.
중복되는 요소는 없고, 오로지 unique 값만 저장하는 자료 구조이다.

7. 해시 테이블
무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.
삽입, 삭제, 탑색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현한다.