자료구조/알고리즘 간단 정리
마지막 업데이트: 2021–12–15
자료구조의 사전적 의미
자료들의 집합을 의미하며, 각 자료들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것
Queue (큐)
First In First Out 로 요소를 저장하는 구조
1, 2, 3, 4 를 넣는다고 하면 { 1, 2, 3, 4 } 로 들어감
Stack (스택)
Last In First Out 로 요소를 저장하는 구조
1, 2, 3, 4 를 넣는다고 하면 { 4, 3, 2, 1 } 로 들어감
Deque (덱)
요소를 양 쪽에서 넣고 뺄 수 있는 구조
Linked List (연결 리스트)
배열의 단점을 보완한 배열
특정한 요소를 저장할 때 해당 요소와, 그 이전 index와 다음 index에 데이터가 위치할(위치 해 있는) 공간의 주소값들을 동시에 저장한다. 다음에 위치할 공간의 주소값은 여러개 일 수 있다. 이렇게 저장되는 요소를 Node 라고 부르고, 0번 째 node는 Head, 마지막 node는 Tail 이라고 부른다.
Tree (트리 ⭐)
위 숫자들은 각각 노드들이다. 트리는 노드가 연결된 구조를 뜻하고, 각각 노드들간의 가지를 Edge(한글로 간선), 들어가는 요소를 키 라고 부른다.
트리는 모든 알고리즘의 기초가 되어 중요하므로 깊은 공부를 추천한다.
Priority Queue (우선순위 큐)
들어간 순서에 상관없이 우선순위가 높은 요소가 먼저 나오는 큐
Heap (힙)
우선순위 큐를 위하여 존재하는(만들어진) 구조
Max Heap (최대 힙)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙
Min Heap (최소 힙)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙
Map (맵)
Key-Value 형태로 요소를 저장하는 구조
Key는 중복이 불가능하고, Value는 중복이 가능함
Set (셋)
요소를 비순차적으로 저장하는 구조
요소들간의 중복이 불가능함
Binary Search (이진 탐색)
요소가 오름차순 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
Binary Search Tree (BST, 이진 탐색 트리)
정렬된 이진 트리로써 다음과 같은 속성을 가지고 있음
- 노드의 왼쪽 하위 트리에는 노드의 키 보다 작은 키가있는 노드만 포함됨
- 노드의 오른쪽 하위 트리에는 노드의 키 보다 큰 키가 있는 노드만 포함됨
- 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 함
- 중복된 키를 허용하지 않음
이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능하다.
Red-Black Tree (레드-블랙 트리)
Balanced BST
간단하게 설명하기엔 너무 방해한 내용이라 [개인적으로 이해 잘 됐던 블로그] 링크 첨부
Tree Map (트리 맵)
Red-Black Tree의 구조로 이루어져 있는 Map
자동으로 정렬을 해주기 때문에 Map보다는 성능이 떨어지지만, 정렬이 필요한 경우에는 더 효율적으로 활용할 수 있다.
Depth-First Search (DFS, 깊이 우선 탐색)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘
Breadth-First Search (BFS, 너비 우선 탐색)
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 알고리즘
BFS vs DFS
