📚 Array vs Linked List
📖 Array
-
논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 원소에 접근이 가능하다. 인덱스로 원소에 접근하는 것은 O(1)의 시간복잡도를 가진다.
▶ 모든 원소에 동일한 시간에 접근할 수 있는 비순차 접근이 가능하다. -
삽입과 삭제의 경우 인덱스에 접근하여 원소를 삽입 또는 삭제하기 위해 그 뒤의 원소들을 앞으로 또는 뒤로 shift 해주어야 하기 때문에 O(n)의 시간복잡도를 가진다.
📖 Linked List
- 각각의 원소들은 다음 원소를 기억하고 있어 연결되어 있는 원소만 바꾸어주면 삽입과 삭제가 가능하다. O(1)의 시간복잡도를 갖는다.
- 그러나 논리적 저장 순서와 물리적 저장 순서가 다르기 때문에 삽입과 삭제 위치를 찾는 것은 O(n)의 시간복잡도를 가진다.
- 결국 모든 행위의 시간복잡도가 O(n)이 된다.
📚 Stack and Queue
📖 Stack
- Last In First Out (LIFO) or First In Last Out (FILO)
📖 Queue
- First In First Out (FIFO)
📚 Tree
계층적 관계를 표현하는 비선형 자료구조
📖 트리 구성요소
- Node(노드): 트리를 구성하는 각각의 요소를 의미
- Edge(간선): 노드와 노드를 연결하는 선
➕
- Root Node(루트 노드): 트리의 최상단 노드
- Terminal Node(=Leaf Node, 단말 노드): 하위에 다른 노드가 연결되어 있지 않은 노드, 트리의 말단 노드
- Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드 (루트 노드 포함)
📖 Binary Tree (이진 트리)
모든 노드가 2개 이하의 자식 노드를 갖는 트리 구조
🌲 Perfect Binary Tree (포화 이진 트리)
모든 레벨의 노드가 꽉 채워진 이진 트리
🌳 Complete Binary Tree (완전 이진 트리)
마지막 레벨을 제외한 모든 레벨의 노드가 꽉 채워진 이진 트리
왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리
🌴 Full Binary Tree (정 이진트리)!
모든 노드가 0개 또는 2개의 자식 노드만을 갖는 이진 트리
출처 : https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
📖 BST (Binary Search Tree)
🤙 데이터 저장 규칙
1) 이진 탐색 트리의 노드에 저장된 키는 유일하다.
2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3) 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
⏳ 탐색 연산 시간 복잡도
O(h), O(log n)
- O(h): 트리의 높이가 h일 때 트리 높이만큼 노드를 탐색해야 한다.
- O(log n): h를 n에 관한 식으로 바꾸면 h = log(n-1) 이다.
한 쪽으로 치우쳐진 트리의 경우에는 최악의 경우 O(n)의 시간복잡도를 갖게 된다.
🗑 삭제
자식 노드가 없는 Leaf Node 삭제
해당 노드를 단순 삭제
자식 노드가 1개인 노드 삭제
해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드 대입
자식 노드가 2개인 노드 삭제
삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 후 해당 노드를 삭제
📚 Binary Heap
Complete Binary Tree(완전 이진 트리)인 자료구조
📖 최대 힙 (Max Heap)
각 노드의 값이 해당 자식 요소의 값보다 크거나 같은(작지 않은) 완전 이진 트리, 트리의 루트는 가장 큰 값
📖 최소 힙 (Min Heap)
최대 힙과 반대로 각 노드의 값이 해당 자식 요소의 값보다 작은 완전 이진트리, 트리의 루트는 가장 작은 값
- Binary Heap은 완전 이진 트리이기 때문에 배열로 구현이 가능하다. (Parent = Children / 2)
- Binary Heap의 원소 삽입, 삭제는 모두 O(log N)의 시간복잡도를 갖는다.
✨ Heapify 구현
📚 RBT (Red Black Tree)
BST를 기반으로 하는 트리 구조, 트리의 깊이를 최소화하여 시간복잡도를 줄이는 자료구조
BST의 삽입, 삭제 연산 과정에서 발생하는 문제를 해결하기 위해 만들어진 자료구조
📖 Red Black Tree의 성질
1) 각 노드는 Red 또는 Black 중 하나의 색이다.
2) Root Node의 색은 Black이다.
3) 각 Leaf Node는 Black이다.
4) 어떤 노드의 색이 Red이면 그 노드의 색은 모두 Black이다.
5) 임의의 노드에 대해서 해당 노드로부터 자손들까지의 모든 path들은 같은 수의 black node를 지난다. (Black-Height가 같아야 한다.)
📖 Red Black Tree의 특징
1) Binary Search Tree이므로 BST의 특징을 모두 갖는다.
2) Root Node로부터 Leaf Node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. (Balanced 상태)
3) 노드의 Child가 없을 경우 Child를 가리키는 포인터는 NIL 값을 저장한다.
📖 RBT의 삽입, 삭제 연산
👉 삽입
- 새로운 노드를 삽입할 때에는 그 노드의 색을 Red로 지정한다. (Black-Height의 변경 최소화)
- 삽입 결과 RBT의 성질을 위배하는 경우 recoloring 또는 restructuring을 통해 조정한다.
- 이러한 과정을 통해 RBT의 성질과 특징을 모두 만족한다.
🔨 Restructuring : 부모의 형제 노드가 Black인 경우
- 삽입된 노드, 부모 노드, 조상 노드를 오름차순으로 정렬
- 중앙 값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
- 부모 노드가 된 노드를 Black으로, 나머지 노드를 Red으로 변환
🎨 Recoloring : 부모의 형제 노드가 Red인 경우
- 삽입된 노드의 부모와 삼촌 노드를 Black으로, 조상 노드를 Red로 변환
- 조상 노드가 루트 노드이면 그대로 Black 유지
- 만약 Red가 연속일 경우 다시 Recoloring 또는 Restructuring 수행
👉 삭제
삭제할 노드의 색을 기억해두고 해당 노드의 색이 Black인 경우에만 트리를 수정
삭제할 노드의 왼쪽 자식 노드만 있는 경우
- 삭제할 노드의 왼쪽 자식 노드를 삭제할 노드로 옮긴다.
삭제할 노드의 오른쪽 자식 노드만 있는 경우
- 삭제할 노드의 오른쪽 자식 노드를 삭제할 노드로 옮긴다.
삭제하려는 노드의 자식 노드가 2개인 경우
- 삭제하려는 노드의 다음 index인 노드를 찾아 색을 저장
- 해당 노드의 오른쪽 자식 노드를 X로 지정
📒 삭제할 노드의 다음 index 노드가 삭제할 노드의 자식인 경우
- X의 부모 노드로 다음 index 노드를 지정
📘 삭제할 노드의 다음 index 노드가 삭제할 노드의 자식이 아닌 경우
- 다음 index 노드와 그 노드의 오른쪽 자식의 위치를 바꾼다.
- X 노드를 삭제할 노드의 오른쪽에 연결한다.
- 삭제할 노드와 다음 index 노드의 위치를 바꾼다.
삭제할 노드의 색에 따라 recoloring
- 삭제하려는 노드가 Red인 경우 : 단순 삭제
- 삭제하려는 노드가 Black인 경우 : 8가지 경우에 따라 다르다...
출처 :
http://kocw-n.xcache.kinxcdn.com/data/document/2021/konyang/choijinmyung0121/7-4.pdf
https://woonys.tistory.com/m/entry/%EC%A0%95%EA%B8%80%EC%82%AC%EA%B4%80%ED%95%99%EA%B5%90-37%EC%9D%BC%EC%B0%A8-TIL-Red-Black-TreeRB%ED%8A%B8%EB%A6%AC-%EC%82%AD%EC%A0%9C-%EA%B5%AC%ED%98%84
📚 Hash Table
- Hash는 내부적으로 배열(인덱스)을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
- 그러나 인덱스로 저장되는 key값이 불규칙하기 때문에 특별한 알고리즘(Hash Function)을 이용해 데이터와 연관된 숫자를 만들어 인덱스로 사용한다.
📖 Hash Function
데이터에 따른 고유한 숫자를 만들어 반환하는 함수
Hash code
Hash Function에 의해 반환된 데이터의 고유 숫자값
Collision
서로 다른 두 개의 키가 같은 인덱스로 hashing되는 것
👉 Collision을 최소화할 수 있는 Hash Function 설계가 중요
📖 Resolve Conflict
Open Address (개방주소법)
해시 충돌이 발생하면 다른 해시 버킷에 해당 자료를 삽입하는 방식
Collision이 발생하면 데이터를 저장할 장소(버킷)를 찾는다.
비어있는 버킷을 찾지 못하면 탐색 시작 위치로 되돌아온다. (Worst case)
1) Linear Probing: 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 진행
2) Quadratic Probing: 2차 함수를 이용해 탐색할 위치를 찾는다.
3) Double Hasing Probing: 하나의 Hash Function에서 충돌이 발생하면 2차 Hash Function을 이용해 새로운 주소를 할당 (많은 연산량)
Separate Chaining (분리 연결법)
Open Addressing보다 빠른 방법
1) 연결 리스트를 사용하는 방식 (Linked List): 각각의 버킷들을 연결 리스트로 만들어 Collision이 발생하면 해당 버킷의 list에 추가하는 방식, 데이터 개수가 적을 경우 사용
2) Tree를 사용하는 방식 (Red-Black Tree): 기본적인 알고리즘은 동일하나 Tree의 메모리 사용량이 많기 때문에 데이터의 양이 많을 경우 사용
데이터의 양
해시 버킷에 6개 이하의 key-value 쌍이 존재한다면 링크드 리스트, 8개 이상의 key-value 쌍이 존재한다면 트리를 사용한다.
📖 해시 버킷 동적 확장
해시 버킷의 개수가 적다면 메모리 사용량은 적지만 해시 충돌로 인한 성능상 손실이 발생한다.
그래서 HashMap은 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 2배로 증가시킨다.
2배로 확장하는 임계점: 현재 데이터 개수가 해시 버킷 개수의 75% 이상이 될 때
📚 Graph
정점과 간선의 집합
📖 관련 용어
-
Undireccted Graph
정점과 간선의 연결관계에 방향성이 없는 그래프 -
Directed Graph
간선에 방향성이 포함되어 있는 그래프
📖 Degree
Undirected Graph
- Degree: 각 정점에 연결된 간선의 개수
Directed Graph
- Outdegree: 각 정점으로부터 나가는 간선의 개수
- Indegree: 각 정점에 들어오는 간선의 개수
📖 가중치 그래프와 부분 그래프
가중치 그래프 (Weight Graph)
간선에 가중치 정보를 두어 구성한 그래프
부분 그래프 (Sub Graph)
전체 그래프의 일부 정점 및 간선으로 이루어진 그래프
📖 그래프를 구현하는 방법
인접 행렬 (Adjacent matrix)
정방 행렬을 사용하는 방법
- 해당하는 위치의 value 값을 통해 정점 간 연결 관계를 O(1)로 파악 가능
- 공간복잡도: O(V^2)
- Dense Graph를 표현할 때 적절한 방법
인접 리스트 (Adjacent list)
연결 리스트를 사용하는 방법
- 정점 간 연결 관계를 확인하는데 오래 걸린다.
- 공간복잡도: O(E+V)
- Sparse Graph를 표현할 때 적절한 방법
📖 그래프 탐색
📒 깊이 우선 탐색 (Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다. 더이상 연결된 정점이 없으면 그 전 단계의 정점으로 돌아간다.(Stack)
📘 너비 우선 탐색 (Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. 방문한 순서를 기록한다. (Queue)
📖 Minimum Spanning Tree
Spanning Tree, 신장 트리: 그래프 내 모든 정점을 포함하는 트리
그래프의 신장 트리 중 최소 연결 트리
특징
- 간선의 가중치의 합이 최소이어야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
📖 Kruskal Algorithm
탐욕적 방법을 이용해 그래프 내 모든 정점을 최소 비용으로 연결하는 최적 해답
동작 순서
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 가장 낮은 가중치를 먼저 선택한다.
- 사이클을 형성하는 간선을 제외한다.
- 해당 간선을 현재의 MST의 집합에 추가한다.
시간 복잡도
O(E log E)
📖 Prim Algorithm
시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법
동작 순서
- 시작 단계에서 시작 정점만 MST 집합에 포함한다.
- 앞에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리 확장한다.
- 가장 낮은 가중치를 먼저 선택한다.
- 위의 과정을 (n-1)개의 간선을 가질 때까지 반복한다.
시간 복잡도
O(n^2)
- 그래프 내에 간선이 적은 Sparse Graph(희소 그래프)의 경우 Kruskal Algorithm 적합
- 그래프 내에 간선이 많이 존재하는 Dense Graph(밀집 그래프)의 경우 Prim Algorithm 적합
출처 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
