자료구조의 기본
Array는 논리적, 물리적 순서가 일치한다.
장점)
index값을 통한 원소 접근이 용이하며, 구현이 쉽다.
단점)
삽입, 삭제 등의 연산에 필요한 cost가 높다.
-> 순서를 맞추기 위해, 원소들을 Shift 연산을 해주어야 하기 때문
Array의 연산에 대한 비효율성을 극복하기 위해 등장.
LinkedList는 논리적으로는 순서대로 되어있으나, 물리적으로 순서대로 되어있지 않음.
각각의 원소가 다음 index위치에 해당하는 물리적 주소를 가지고 있다.
데이터를 shift할 필요 없이 해당 원소의 주소만 변경하면 된다.
단점)
이러한 특징 때문에 index를 참조하려면, 1번 index부터 차례대로 접근해야 한다.
선형 자료구조의 일종으로, FILO(First in Last Out)
처음에 들어간 원소가 가장 아래에서 부터 차례로 위치,
따라서 가장 늦게 나옴.
미로찾기, 괄호 유효성 체크등에 활용된다.
역시 선형자료 구조이고, Stack과는 반대로 FIFO(First in first out)이 적용됨.
작업 우선순위, Heap 구현등에 사용됨.
Stack, Queue와는 다르게 비선형 자료구조, 계층적 구조를 표현하는 자료구조이다.
구성요소는 Node, Edge, Root, Terminal, Internal이 있다.
Node : 트리를 구성하고 있는 원소 그 자체
Edge : 노드와 노드사이를 잇는 선
Root : 트리에서 최상위 노드
Terminal : 최하위 노드이다, Leaf Node라고도 함.
Internal : 최하위 노드를 제외한 모든 노드.
Root노드를 포함, Leaf노드를 제외한 모든 노드의 자식이 두 개인 것을 의미함.
공집합 역시 노드로 인정, 노드로 이루어진 각 층을 Level이라 하며, Level 수를 이 트리의 height라 한다.
Full Binary Tree ( 포화 이진 트리 )
Complete Binary Tree ( 완전 이진 트리 )
두 가지 종류가 있음.
-> 두 종류의 차이점 알아보기
parent(i) = i/2,
left_child = 2i ,
right_child = 2i + 1
의 인덱스 값을 가진다.
효율적인 탐색 방법만이 아니라, 효율적인 저장 방법도 고민해야한다.
이진 탐색 트리는 이진트리이며, 데이터를 저장하는 특별한 규칙이 있다.
그 규칙으로 데이터를 검색할 수 있다.
값이 추가되고 삭제 됨에 따라, 한 쪽에만 치우친 Skewed Tree(편향 트리)가 될 가능성이 있다.
이를 해결하기 위해 Rebalancing이라는 기법을 사용하여 트리를 재조정하게 된다.
RBT는 Rebalancing 기법의 하나로, 기존 이진 탐색 트리의 삽입, 삭제 탐색의 비효율성을 개선한 방법이다.
RBT의 특징
새로 삽입한 노드를 BST 특성을 유지하며 삽입한 후, 색을 Red로 칠한다.
-> Black-height의 수를 최대한 유지하기 위해서이다.
만일, Black-height 특성이 깨지면, Rotation을 통해 조정한다.
삭제과정도 삽입과 같고, 삭제될 노드의 Child 색은 Rotation으로 정해진다.
이는 배열에 기반한 이진 탐색 트리이며,
Max-Heap과 Min-Heap가 있다.
Max-Heap은 상위 노드의 값이 하위노드의 값보다 크며,
Min-Heap은 반대로 상위 노드의 값이 하위노드의 값보다 작다.
최대값, 최솟값을 찾는데 용이함.
평균적으로 빠른 탐색 속도를 갖는다.
충돌을 고려하지 않았을 경우 빠름.
Key값을 해시함수를 통해 인덱스로 변환, 그 인덱스에 집어 넣는다.
만약 다른 Key값을 해시함수를 통과시켰는데 같은 인덱스가 나온다면, 이것을 충돌이라 한다.
Hashmap의 Resize : 일정 개수이상 크기가 커지면, 해시 버킷의 크기를 두 배로 늘림.
정점과 간선의 집합이며, 일종의 Tree이다.
Undirected와 Directed Graph가 있는데, 방향성 유무로 결정된다.
Degree란 Undirectd Graph에서 정점에 연결된 간선의 개수이다.
Directed Graph에서의 Degree는 방향성이 있기 때문에 둘로 나뉘는데,
나가는 간선의 개수는 Outdegree, 들어오는 간선의 개수를 Indegree라 한다.
가중치 그래프 란 간선에 가중치를 둔 그래프, 부분 그래프 란 한 그래프의 일부 정점 및 간선으로 이루어진 그래프.
그래프의 구현 방법
1. 인접 행렬 : 정방 행렬을 사용하여 구현.
연결 관계를 O(1)로 파악 가능.
공간 복잡도는 O(2V)
탐색 방법에는 깊이 우선 탐색(DFS, Depth First Search)와 너비 우선 탐색(BFS, Breadth First Search)이 있다.
깊이 우선 탐색은 말 그대로 깊숙히 들어가서 탐색하고 나오는 것이며,
유용한 자료구조는 Stack이다.
너비 우선 탐색은 임의의 한 정점에 대해 인접한 정점을 queue에 넣고(enqueue), dequeue연산에서 나온 하나의 정점으로 들어가서 그 정점의 인접한 정점을 다시 Queue에 넣어서 탐색하는 방식.
BFS로 찾은 경로는 최단 경로이다.