목차
- 복잡도
- 선형 자료 구조
- 비선형 자료 구조
복잡도
시간 복잡도
문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킵니다.
어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타 냅니다.
존재 이유 : 효율적인 코드로 개선하는 데 쓰이는 척도
빅오 표기법
입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말합니다.
정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함합니다.
선형 자료 구조
요소가 일렬로 나열되어 있는 자료 구조를 말합니다.
연결 리스트
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
삽입 삭제 : O(1)
탐색 : O(n)
총 3가지의 리스트가 존재합니다.
- 싱글 연결 리스트 : next 포인터만 가집니다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말합니다.
배열
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다.
중복을 허용하고 순서가 있습니다.
배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용합니다.
랜덤 접근과 순차적 접근
@TODO
배열과 연결 리스트 비교
배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있습니다.
연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나의 상자 내부를 확인해봐야 합니다.
배열 : 랜덤 접근이 가능하다. O(1)
연결 리스트 : 랜덤 접근이 불가능 하다. O(n)
결론 :
| 속도 | 배열 | 연결 리스트 |
|---|---|---|
| 탐색 | 빠름 | 느림 |
| 추가&삭제 | 느림 | 빠름 |
벡터
동적으로 요소를 할당할 수 있는 동적 배열입니다.
중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다.
탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제, 삽입하는 데 O(n)의 시간이 걸립니다.
push_back()을 할 때 매번 크기가 증가하는 것이 아니라 공간이 꽉차면 2의 제곱승 + 1 마다 크기를 2배로 늘립니다.
ex) 1, 3, 5, 9, 17번 째에 공간을 2배 확장합니다.
| 순서 | 용량 | 비용 |
|---|---|---|
| push_back(1) | 1 | 1 |
| push_back(2) | 2 | 1+1 |
| push_back(3) | 4 | 2+1 |
| push_back(4) | 4 | 1 |
| push_back(5) | 8 | 4+1 |
| push_back(6) | 8 | 1 |
| push_back(7) | 8 | 1 |
| push_back(8) | 8 | 1 |
| push_back(9) | 16 | 8+1 |
★에서 공간이 2배 확장합니다.
※ 비용 : i번째 push_back()할 때 드는 비용
스택
가장 마지막으로 들어간 데이터가 가장 빨리 나오는 성질 (LIFO, Last In First Out)을 가진 자료 구조 입니다.
재귀함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰입니다.
삽입 및 삭제 : O(1)
탐색 O(n)
큐
먼저 넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료구조입니다.
프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됩니다.
삽입 및 삭제 : O(1)
탐색 O(n)
비선형 자료구조
일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다.
일반적으로 트리나 그래프를 말합니다.
그래프
정점과 간선으로 이루어진 자료 구조를 말합니다.
정점과 간선
어떠한 곳에서 어떠한곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점(vertex)가 되고 '무언가'는 간선(edge)이 됩니다.
'무언가'로부터 나가는 '간선' : outdegree
'무언가'로부터 들어오는 '간선' : indegree
정점과 간선으로 이루어진 집합을 그래프라고 합니다!
※ 가중치 : 간선과 정점 사이에 드는 비용을 뜻합니다.
트리
그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 루트 노드, 내부 노드, 리프 노드 등으로 구성됩니다.
트리로 이루어진 집합을 숲이라고 합니다.
트리의 특징
- 부모, 자식 계층 구조를 가집니다.
- 간선 수 = 노드 수 - 1
- 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있습니다.
트리의 구성
루트 노드 : 가장 위에 있는 노드
내부 노드 : 루트 노드와 내부 노드 사이에 있는 노드
리프 노드 : 자식 노드가 없는 노드
깊이 : 루트 노드로부터 특정 노드까지 최단 거리로 갔을 떄의 거리를 말합니다.
높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미합니다.
레벨 : 보통 깊이와 같은 의미를 갖습니다.
문제마다 조금씩 다릅니다. 1번 노드를 0레벨이라 할 수 있고, 2번 노드까지를 1레벨이라고 할 수 있습니다.
서브트리 : 트리 내의 하위 집합을 말합니다.
이진 트리
자식의 노드 수가 두 개 이하인 트리를 의미합니다.
정이진 트리 : 자식 노드가 0 또는 두 개인 이진 트리
완전 이진 트리 : 왼쪽부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
변질 이진 트리 :자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리
이진 탐색 트리
BST는 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리를 말합니다.
왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면 된다는 것을 자명합니다.
보통 요소를 찾을 때 BST는 O(logn)이 걸립니다. 하지만 최악의 경우 O(n)이 걸립니다.
AVL 트리
Adelson-Velsky and Lanis tree는 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리입니다.
두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다.
탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡습니다.
레드 블랙 트리
균형 이진 탐색트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)입니다.
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용됩니다.
"모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 "라는 규칙이 있습니다.
사용된 자료구조 : C++ STL의 set, multiset, map, multimap
힙
완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있습니다.
최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 합니다.
최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 합니다.
최대힙의 삽입
힙에 새로운 요소가 들어오면, 일단 마지막 노드에 삽입합니다.
이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킵니다.
최대힙의 삭제
최대힙에서 최대값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성됩니다.
우선순위 큐
우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조입니다.
힙을 기반으로 구현되었습니다.
맵
특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조입니다.
해시 테이블을 구현할 때 쓰며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두 가지가 있습니다.
셋
특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 유니크 값만 저장하는 자료구조입니다.
해시 테이블
무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다.
삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가집니다.
