반응형
1. 해시테이블
- 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조
구현
충돌
- 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.
- 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다.
👉🏻 입력값이 달라도 똑같은 결과가 나오면 충돌 - 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다.
- 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식
- 체이닝은 충돌 발생 시 ‘연결’해가는 것
- 오픈 어드레싱 O(1)
- 체이닝 O(n)
- 오픈 어드레싱은 값이 뭉치는 클러스터링이 발생할 수 있고,
- 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점
- 그래서 각 언어 별로 해시테이블의 구현 방식이 다른데요. C++, Java, Go는 체이닝을 택하고 Python, Ruby는 오픈 어드레싱을 택하고 있다.
구현 (Python)
- 체이닝 방식의 해시테이블
# structures.py
class HashTable:
def __init__(self):
self.size = 10 # 해시테이블의 사이즈 (10으로 나눈 나머지이기떄문에 10으로 설정)
self.table = [None] * self.size
def _hash_function(self, key):
return key % self.size
def put(self, key, value):
index = self._hash_function(key) # 키를 넣었을 때 결과값
if self.table[index] is None: # 값이 없을 때 (푸시한적이 없는 해싱값일 때)
self.table[index] = HashNode(key, value)#next=None
else: # 이미 값이 있을 때 (푸시한적이 있는 해싱값일 때) - 체이닝방식이므로 같은 값은 맨 끝에 계속 붙여주면 됨
node = self.table[index]
while node.next is not None: # 다음 노드가 없을 때 까지(맨끝까지)
node = node.next
node.next = HashNode(key, value)
def get(self, key):
index = self._hash_function(key)
node = self.table[index]
while node is not None: #노드에 배정된 키가 있을 동안
if node.key == key: #내가 원하는 값(내가 넣은 키라면)
return node.value #값 반환
node = node.next #원하는 노드가 아니면 옮기자
return -1 # 배정된 게 없다면 -1 반환하자
def remove(self, key):
index = self._hash_function(key)
node = self.table[index]
prev_node = None
while node is not None:
if node.key == key:
if prev_node is None: # 이전 노드가 없다 - 첫번째꺼다 - 지금거를 다음걸로 바꾼다
self.table[index] = node.next
else:
prev_node.next = node.next # 이전 노드의 next를 지금거의 다음걸로 넘긴다 (가운데를 빼는 느낌)
return
prev_node = node # 이전 노드를 지금 노드로 넘긴다
node = node.next
# test.py
ht = HashTable()
ht.put(1, 1)
ht.put(2, 2)
assert ht.get(1) == 1
assert ht.get(2) == 2
assert ht.get(3) == -1
ht.put(12, 1)
ht.put(22, 2)
ht.put(32, 3)
assert ht.get(12) == 1
assert ht.get(22) == 2
assert ht.get(32) == 3
ht.remove(12)
assert ht.get(2) == 2
assert ht.get(12) == -1
assert ht.get(22) == 2
assert ht.get(32) == 3
ht.get(2)
2. 트리
- 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점
- 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점
트리 용어
- Node: 트리에서 데이터를 저장하는 기본 요소
- Root Node: 트리 맨 위에 있는 노드
- Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
- Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
- Child Node: 어떤 노드의 하위 레벨에 연결된 노드
- Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝)
- Sibling: 동일한 Parent Node를 가진 노드
- Depth: 트리에서 Node가 가질 수 있는 최대 Level
트리의 종류
이진트리
- 각 노드가 최대 두 개의 자식을 가지는 트리
- 하위 노드가 3개 이상일 수 없다. 무조건 0,1,2개
o Level 0
o o o Level 1
o o o Level 2 # 이진 트리(X)
o Level 0
o o Level 1
o o o Level 2 # 이진 트리(O)
완전 이진 트리 (Complete Binary Tree)
- 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다
o Level 0
o o Level 1
o o Level 2 # -> 이진 트리 O 완전 이진 트리 X
o Level 0
o o Level 1
o o o Level 2 # -> 이진 트리 O 완전 이진 트리 O
완전 이진 트리를 배열로 표현
트리 구조를 표현하는 방법
- 직접 클래스 구현
- 배열로 표현 -> 완전 이진 트리를 쓰는 경우에 가능!
- 왼쪽부터 데이터가 쌓이므로, 이를 순서대로 배열에 쌓으면서 표현
완전 이진 트리 배열로 표현하기
- 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않음
- 그래서 None 값을 배열에 넣고 시작한다. [None]
- 8의 자식 6,3 / 6의 자식 4,2 / 3의 자식 5
8 Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
6 3 Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!
배열 = [None, 8, 6, 3, 4, 2, 5]
- 왼쪽에 있는 자식의 인덱스 : 현재 인덱스 * 2
- 8 : 1번 / 6 : 1 * 2 = 2번
- 6 : 2번 / 4 : 2 * 2 = 4번
- 오른쪽 자식의 인덱스 : 현재 인덱스 * 2 + 1
- 8 : 1번 / 3 : 1 * 2 + 1 = 3번
- 6 : 2번 / 2 : 2 * 2 + 1 = 5번
- 부모 인덱스 : 현재 인덱스 // 2
- 3 : 3번 / 3 // 2 = 1번 : 8
- ==부모를 찾을 수 있다!==
완전 이진 트리의 높이
트리의 높이
루트 노드부터 가장 아래 리프 노드까지의 길이높이가 2인 트리
o Level 0 # 루트 노드
o o Level 1
o o o Level 2 # 가장 아래 리프 노드
이 트리의 높이는 ? 2 - 0 = 2!
각 레벨에 노드가 꽉 차 있는 경우
1 Level 0 -> 1개
2 3 Level 1 -> 2개
4 5 6 7 Level 2 -> 4개
8 9....... 14 15 Level 3 -> 8개
Level k -> 2^k 개
👉 레벨이 k라면, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k이다.
노드가 꽉 찬 완전 이진 트리의 모든 노드 개수
- 높이 h
- 각 레벨k 의 노드 2^k개
레벨은 1, 2, 3, ... , h 이므로 모든 노드의 개수는
1 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^h
= 2^(h+1) - 1
👉 높이가 h라면, 최대 노드 개수는 2^(h+1) -1개가 된다.
[!최대 노드 개수가 N이라면 h는?]
2^(h+1) -1 = N
→ h = log_2(N+1)-1
👉 완전 이진 트리 노드의 갯수가 N일 때, 높이는 최대 O(logN)
3. 힙 (Heap)
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Tree)(Complete Binary Tree)
- 최대/최소의 값들이 필요한 연산에 사용
- Max 힙 : 최댓값이 맨 위
- Min 힙 : 최솟값이 맨 위
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!
최대 힙 - 삽입 알고리즘
- 원소를 맨 마지막에 넣는다.
- 부모 노드와 비교, 더 크면 자리 바꾸기
- 부모 노드보다 작거나 가장 위에 도달하지 않을 때 까지 반복
이 맥스 힙에서 9를 추가해보겠습니다!
8 Level 0
6 3 Level 1
4 2 1 Level 2
1. 맨 마지막에 원소를 넣습니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
최대 힙 - 삽입 시간 복잡도
완전 이진트리 최대 높이 : O(log(N))
-> 반복하는 최대 횟수 : O(log(N))
-> Max 힙의 원소 추가는 O(log(N)) 의 시간 복잡도
최대 힙 - 삽입 구현
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def insert(self, k):
self.items.append(k)
self._percolate_up()
def _percolate_up(self):
# percolate: 스며들다.
cur = len(self.items) - 1
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
최대 힙 - 추출
최대 힙에서 원소를 추출하는 방법 : 루트 노드(최댓값) 삭제 👉 맨 위 원소만 삭제 가능
이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
3 Level 0
7 6 Level 1
2 5 4 8 Level 2
2. 맨 뒤에 있는 원소를 삭제합니다.
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!
3 Level 0
6 7 Level 1
2 5 4 X Level 2
3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다.
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.
3 Level 0
6 7 Level 1
2 5 4 Level 2
7 Level 0
6 3 Level 1
2 5 4 Level 2
3-2. 다시 자식 노드와 비교합니다.
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.
7 Level 0
6 3 Level 1
2 5 4 Level 2
7 Level 0
6 4 Level 1
2 5 3 Level 2
4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!
7 Level 0
6 4 Level 1
2 5 3 Level 2
5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!
최대 힙 - 추출 시간 복잡도
O(log(N))
최대 힙 - 구현
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def insert(self, k):
self.items.append(k)
self._percolate_up()
def _percolate_up(self):
# percolate: 스며들다.
cur = len(self.items) - 1
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
def extract(self):
if len(self.items) - 1 < 1:
return None
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1
if left <= len(self.items) - 1 and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self.items) - 1 and self.items[right] > self.items[biggest]:
biggest = right
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
4. 그래프 (Graph)
- 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점
- 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점
- 그래프 : 연결 관계에 초점
- 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex)
- 간선(Edge): 노드 간의 관계를 표시한 선
- 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)
유방향 그래프 (Directed Graph)
- 방향이 있는 간선
- 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능
무방향 그래프 (Undirected Graph)
- 방향이 없는 간선
그래프의 표현 방법
- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
- 인접 리스트(Adjacnecy List): 연결리스트 (Linked List)로 그래프의 연결 관계를 표현
- 제니 : 0 , 르탄 : 1 , 로제 : 2 , 사나 : 3
로제 - 사나
⎜
제니 - 르탄
2 - 3
⎜
0 - 1
이를 인접 행렬, 2차원 배열로 나타내면
2 - 3
⎜
0 - 1
0 1 2 3
0 X O X X
1 O X O X
2 X O X O
3 X X O X
이를 배열로 나타내면
graph = [
[False, True, False, False],
[True, False, True, False],
[False, True, False, True],
[False, False, True, False]
]
인접 리스트로 표현
- 인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장
2 - 3
⎜
0 - 1
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2
이를 딕셔너리로 표현하면
graph = {
0: [1],
1: [0, 2]
2: [1, 3]
3: [2]
}
이 두 방식의 차이?
👉 시간 VS 공간
- 인접 행렬으로 표현 : 연결 여부를 즉각적으로 알 수 있다.
- 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간 사용
- 인접 리스트로 표현 : 연결 여부를 알기 위해선 각 리스트를 돌아야 함
- 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간 사용
- 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간만 사용
반응형
'Computer Science > 자료구조, 알고리즘' 카테고리의 다른 글
| 최단 경로 문제 - 다익스트라(Dijkstra) 알고리즘 (0) | 2024.07.11 |
|---|---|
| 동적계획법 - DP (Dynamic Programming) (0) | 2024.07.11 |
| 파이썬 - 리스트, 집합, 딕셔너리 시간복잡도 정리 (0) | 2024.07.11 |
| 자료구조 - 배열, 연결리스트, 스택, 큐 정리 (2) | 2024.07.10 |
| 탐색 알고리즘 - DFS와 BFS (1) | 2023.08.14 |