[CS] 자료구조 요약

1. 자료 구조란?

- 데이터를 저장하거나 조직하는 방법

- 데이터의 집합과 데이터 간의 관계

 

 

2. 복잡도

1) 시간 복잡도

빅오 표기법

- 입력 데이터에 대한 최악의 실행 시간을 표시한다.

※ 실행 시간이 너무 커지는 경우까지 대비해야 한다.

- 코드의 효율성을 따질 때 유용하게 쓰인다.

 

2) 공간 복잡도

- 필요한 자원 공간의 양을 의미한다.

- 정적, 동적으로 생성된 공간 모두를 포함하여 계산한다.

 

 

3. 선형 자료 구조

- 일렬로 나열되어 있는 자료 구조

 

1) 연결 리스트

- 데이터를 감싼 노드들을 포인터로 연결하는 구조

- 장점 : 인덱스 없이 노드들끼리 연결만 되어 있기 때문에 삽입과 삭제가 빠르다.

- 단점 : 탐색은 데이터를 저장한 순서대로 하기 때문에 느리다.

 

2) 배열

- 타입이 같은 데이터들의 집합

- 중복을 허용하며 순서가 있음

- 장점 : 특정 인덱스에 해당하는 데이터에 직접 접근할 수 있기 때문에 탐색이 빠르다.

- 단점 : 삽입과 삭제는 뒤에 있는 모든 데이터를 옮겨야 하기 때문에 느리다.

 

3) 벡터

- 동적 할당이 가능한 배열

- C++의 벡터(#include <vector>)에서는 맨 뒤에 요소를 더하는 push_back(), 맨 뒤의 요소를 지우는 pop_back(), 특정 요소를 지우는 erase(), 특정 요소를 찾는 find(), 벡터를 초기화하는 clear() 함수를 제공한다.

 

4) 스택

- 하나의 입출구를 가진 자료 구조로, LIFO(Last In First Out) 성질을 가진다.

 

5) 큐

- 입구와 출구가 다른 자료 구조로, FIFO(First In First Out) 성질을 가진다.

 

 

4. 비선형 자료 구조

- 일렬로 나열되어 있지 않은 자료 구조

 

1) 그래프

- 정점과 간선으로 이루어진 자료 구조

- 두 정점 사이를 오가는 비용을 가중치라고 한다.

 

 

2) 트리

- 그래프와 마찬가지로 정점과 간선으로 이루어져 있으나, 계층적이며 사이클이 없는 구조라는 차이점이 있다.

- 간선 수 = 정점 수 - 1

- 루트 노드(부모가 없는 노드), 리프 노드(자식이 없는 노드), 내부 로드(루트 노드와 리프 노드 사이의 노드)로 이루어져 있다.

 

주요 트리

- 이진 트리 : 모든 노드가 2개 이하의 자식 노드를 갖는 트리

- 이진 탐색 트리 : 왼쪽 서브 트리에는 현재 노드 값보다 작은 값들만 있고, 오른쪽 서브 트리에는 현재 노드 값보다 큰 값을만 있는 트리

- AVL 트리 : 이진 탐색 트리가 선형적인 트리가 되는 최악의 경우(이미지 참고)를 방지하기 위해, 트리 일부를 회전 시키며 균형을 잡는 균형 이진 트리다. 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logN)이다.

※ 균형 이진 트리 : 왼쪽/오른쪽 노드의 높이 차이가 1 이하인 트리

이진 탐색 트리의 최악의 경우 - O(N)

- 레드 블랙 트리 : 레드/블랙 색상을 도입하여 트리의 균형을 맞추는 균형 이진 트리로, 루트 노드와 모든 리프 노드는 블랙이고 레드 노드의 자식은 반드시 블랙 노드라는 규칙을 기반으로 균형을 잡는다. 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logN)이며, C++ STL의 map, set에 사용된다.

 

 

3) 힙

- 완전 이진 트리 기반의 자료 구조로, 상위 노드 값이 항상 큰 최대힙과 상위 노드 값이 항상 작은 최소힙 2가지가 있다.

※ 완전 이진 트리 : 왼쪽에서부터 채워지는 이진 트리

- 삽입 : 새로운 노드를 힙의 마지막 노드에 두고, 상위 노드들과 비교하며 교환해서 힙의 성질을 만족시킨다.

- 삭제 : 삭제된 노드의 자리에 마지막 노드를 둔 뒤에 스왑 등의 과정을 거쳐 재구성한다.

 

 

4) 우선순위 큐

- 우선순위가 높은 요소가 가장 앞에 위치하도록 만든 자료 구조

- 힙을 기반으로 구현된다.

 

 

5) Map

- key-value 쌍으로 이루어진 자료 구조

- 정렬을 보장하지 않는 맵과 정렬을 보장하는 맵이 있다.

 

 

6) Set

- 고유한 요소를 저장하는 자료 구조로, 중복을 허용하지 않는다.

 

 

7) 해시 테이블★

- key-value 쌍으로 이루어졌으며, 내부적으로 버킷이라고 부르는 내부 배열들을 사용하는 자료 구조다.

- key에 해시함수를 적용해서 고유한 index를 만들고, 이 index를 기반으로 어느 버킷에 데이터를 저장할 지 결정한다. 도서관에서도 분류 번호를 통해 원하는 책을 빨리 찾을 수 있듯이, 해시 테이블도 여러 버킷을 통해 데이터들을 분류해놓기 때문에 매우 빠르게 데이터를 찾을 수 있다.

- 탐색, 삽입, 삭제 모두 평균 O(1)의 시간복잡도를 가진다.

- key는 해시값으로 변환되어 저장되기 때문에 메모리도 적게 차지한다.

 

 

 

5. 수식의 표기법

- 전위 표기법 : 연산자를 앞에 표기하는 방법

- 중위 표기법 : 연산자를 가운데에 표기하는 방법

- 후위 표기법 : 연산자를 뒤에 표기하는 방법

 

 

 

6. 정렬

- 삽입 정렬 : 이미 순서화된 요소 사이에 요소를 순서에 맞게 삽입시켜 정렬

- 선택 정렬 : 최소값을 선택해서 앞쪽에 두어가며 정렬

- 버블 정렬 : 인접한 두 개의 요소를 비교해서 교환해나가며 정렬

- 퀵정렬 : 분할정복을 이용한 정렬

- 힙 정렬 : 전이진 트리를 이용한 정렬

- 합병 정렬 : 이미 정렬되어 있는 묶음을 합병해나가며 정렬