비선형 자료구조
일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조. 트리, 그래프등
그래프
정점과 간선으로 이루어진 자료 구조
정점과 간선
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다
-> 어떠한곳 = 정점(vertex)
-> 무언가 = 간선(edge)
예를들어 그림처럼 어떤 아파트로 간다고 하면
아파트 = 하나의 정점
가는 길 = 간선
- 단방향 간선 : 한 방향으로만 갈 수 있는 간선
- 양방향 간선 : 양쪽으로 서로 갈 수 있는 간선
outdegree : 정점으로 나가는 간선
indegree : 들어오는 간선
위 그림의 정점 V는 outdegree 3개, indegree 2개 인 상태
정점은 약자로 V or U를 사용한다.
보통 어떤 정점으로부터 어떤 정점까지 간다 = 'U에서 V로간다'
라고 표현한다.
이렇게 정점과 간선으로 이루어진 집합을 그래프 라고 한다.
가중치
간선과 정점 사이에 드는 비용
1 -> 2 노드로 가는 비용이 한 칸이라면 1->2 노드까지의 가중치: 한 칸
ex) 성남이라는 정점에서 네이버라는 정점까지 가는데 걸리는 택시비가 13000원이라면 성남->네이버 까지의 가중치 : 130000원
파이썬 예시
class Graph:
# 딕셔너리를 사용하여 그래프를 저장.
# 키는 정점, 값은 인접한 정점들의 리스트.
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
if vertex not in self.graph: # 정점이 그래프에 없으면
# 그 정점을 그래프에 추가하고 빈 리스트를 값으로 설정.
self.graph[vertex] = []
def add_edge(self, vertex1, vertex2):
# 두 정점이 모두 그래프에 존재하면
if vertex1 in self.graph and vertex2 in self.graph:
# vertex1의 인접 리스트에 vertex2를 추가.
self.graph[vertex1].append(vertex2)
# vertex2의 인접 리스트에 vertex1을 추가 (무향 그래프).
self.graph[vertex2].append(vertex1)
def display(self):
for vertex in self.graph: # 그래프의 모든 정점에 대해
# 정점과 그에 연결된 인접 정점들을 출력.
print(f"{vertex} -> {self.graph[vertex]}")
# 그래프 생성
g = Graph()
# 정점 추가
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')
# 간선 추가
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
#결과
A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C']
트리
트리는 그래프의 일종이며 다음 특징을 가진다.
-
부모, 자식 계층 구조를 가진다. 그림에서는 5번노드 = 6,7의 부모노드
6,7 = 5번의 자식노드. 위에있으면 부모, 아래있으면 자식노드 -
V - 1 = E라는 특징이 있다. (간선 노드수 - 1)
-
임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉 트리 내의 어떤노드와 어떤노드까지의 경로는 반드시 존재한다.
트리의 구성
루트노드, 내부노드, 리프노드
루트노드
가장 위에 있는 노드. 보통 트리 탐색할 때 루트노드 중심으로 탐색하면 쉽게 풀리는 경우가 많다.
내부노드
루트노드와 리프노드사이에 있는 노드
리프노드
자식노드가 없는 노드
트리의 높이와 레벨
- 깊이 : 루트노드로부터 특정 노드까지의 최단거리
- 높이 : 루트노드부터 리프노드까지 거리 중 가장 긴 거리
- 레벨 : 깊이와 같은 의미로 생각하면됨(구체적인 차이는 필요시 공부)
- 서브트리 : 트리 내의 하위 집합
이진 트리의 종류
이진 탐색 트리
노드의 오른쪽 하위트리에는 '노드 값보다 큰 값'이 있고, 왼쪽 하위 트리에는 '노드값 보다 작은 값'이 들어있는 트리.
왼쪽 : 작은값
오른쪽 : 작은값
으로 계속 내려간다. 이렇게 하면 검색을 하기에 용이하다.
보통 이진 탐색 트리의 경우 탐색에 O(logn)이 걸린다. (최악의경우 O(n))
최악의 경우 O(n)이 나올 수 있는 이유
AVL트리
Adelson-Velsky and Landis tree.
앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다는 특징이 있다.
탐색,삽입,삭제 모두 시간복잡도 : O(logn)
균형이 안 맞을 때 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.
레드 블랙 트리
균형 이진 탐색 트리중 하나.
탐색,삽입,삭제 모두 시간복잡도 : O(logn)
각 노드는 빨간색 or 검은색을 나타내는 추가 비트를 저장하며 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용된다.
규칙
-> 모든 리프 노드와 루트노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
파이썬 예시(이진탐색트리)
class Node:
def __init__(self, key):
self.left = None # 왼쪽 자식 노드를 초기화
self.right = None # 오른쪽 자식 노드를 초기화
self.val = key # 노드의 값을 초기화
class BinarySearchTree:
def __init__(self):
self.root = None # 트리의 루트 노드를 초기화
def insert(self, key):
if self.root is None:
# 루트 노드가 없으면 새로운 노드를 루트로 설정
self.root = Node(key)
else:
# 루트 노드가 있으면 재귀적으로 삽입
self._insert(self.root, key)
def _insert(self, root, key):
if key < root.val: # 삽입할 값이 현재 노드의 값보다 작으면
if root.left is None:
# 왼쪽 자식 노드가 없으면 새로운 노드를 왼쪽 자식으로 설정
root.left = Node(key)
else:
# 왼쪽 자식 노드가 있으면 왼쪽 서브트리에 삽입
self._insert(root.left, key)
else:
if root.right is None:
# 오른쪽 자식 노드가 없으면 새로운 노드를 오른쪽 자식으로 설정
root.right = Node(key)
else:
# 오른쪽 자식 노드가 있으면 오른쪽 서브트리에 삽입
self._insert(root.right, key)
def inorder_traversal(self, root, result):
if root:
self.inorder_traversal(root.left, result) # 왼쪽 서브트리 순회
result.append(root.val) # 현재 노드의 값을 결과 리스트에 추가
self.inorder_traversal(root.right, result) # 오른쪽 서브트리 순회
def search(self, key):
# 루트 노드에서부터 시작하여 키를 검색
return self._search(self.root, key)
def _search(self, root, key):
if root is None or root.val == key:
return root # 노드가 없거나 값을 찾으면 해당 노드를 반환
if key < root.val:
# 왼쪽 서브트리에서 재귀적으로 검색
return self._search(root.left, key)
# 오른쪽 서브트리에서 재귀적으로 검색
return self._search(root.right, key)
def display(self):
result = []
# 중위 순회를 통해 트리의 값을 정렬된 순서로 얻음
self.inorder_traversal(self.root, result)
print(result) # 결과 리스트 출력
# 예제 사용
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Inorder traversal of the BST:")
bst.display()
# 탐색 예제
print("Search for 40:", bst.search(40) is not None)
print("Search for 25:", bst.search(25) is not None)
#결과
Inorder traversal of the BST:
[20, 30, 40, 50, 60, 70, 80]
Search for 40: True
Search for 25: False결과
힙
힙은 완전 이진 트리 기반의 자료구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리이다.
-
최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야한다.
-
최소힙 : 최소힙에서 루트노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야한다. 또한, 각 노드의 자식노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야한다.
최대힙의 삽입
힙에 새로운 요소가 들어온다 -> 새로운 노드를 힙의 마지막 노드에 이어서 삽입 -> 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킴.
최대힙의 삭제
최대힙에서 최댓값은 루트노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성된다.
파이썬 예시(heapq사용)
import heapq
class MinHeap:
def __init__(self):
self.heap = [] # 힙을 빈 리스트로 초기화합니다.
def insert(self, key):
# heapq.heappush를 사용하여 힙에 새로운 키를 추가합니다.
heapq.heappush(self.heap, key)
def extract_min(self):
if not self.heap:
return None # 힙이 비어 있으면 None을 반환합니다.
# heapq.heappop을 사용하여 힙의 최소값을 제거하고 반환합니다.
return heapq.heappop(self.heap)
def display(self):
print(self.heap) # 현재 힙의 상태를 출력합니다.
# 예제 사용
heap = MinHeap()
heap.insert(3) # 힙에 3을 삽입합니다.
heap.insert(1) # 힙에 1을 삽입합니다.
heap.insert(6) # 힙에 6을 삽입합니다.
heap.insert(5) # 힙에 5를 삽입합니다.
heap.insert(2) # 힙에 2를 삽입합니다.
heap.insert(4) # 힙에 4를 삽입합니다.
print("Heap elements:") # 현재 힙의 상태를 출력합니다.
heap.display()
#결과
Heap elements:
[1, 2, 4, 5, 3, 6]
print("Extract min:", heap.extract_min()) # 최소값을 추출하고 출력합니다.
print("Heap after extracting min:") # 최소값 추출 후 힙의 상태를 출력합니다.
heap.display()
#결과
Extract min: 1
Heap after extracting min:
[2, 3, 4, 5, 6]
print("Extract min:", heap.extract_min()) # 다시 최소값을 추출하고 출력합니다.
print("Heap after extracting min:") # 최소값 추출 후 힙의 상태를 다시 출력합니다.
heap.display()
#결과
Extract min: 2
Heap after extracting min:
[3, 5, 4, 6]
알고리즘 문제를 풀 때 최소힙을 구현하는 방식만 알고 있으면 최대힙을 구할 때는 마이너스(-) 를 붙여서 최대힙처럼 사용할 수 있다. (둘 중에 하나만 할 줄 알면 됨)
