그래프(Graph)란?실제 세계의 현상이나 사물을 노드와 간선으로 표현한 자료구조 그래프 관련 용어노드(Node): 위치 (= 정점, Vertex)간선(Edge): 위치 간의 관계를 표시한 선, 노드를 연결한 선 (= Link, Branch)인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 ※ 참고 용어정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수단순 경로(Simple Path): 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로사..

힙 구현 일반적으로 힙 구현시 배열을 활용 힙 구현의 편의를 위해, 루트 노드 인덱스를 1로 지정함 부모 노드 인덱스 = (자식 노드 인덱스) // 2 왼쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2 오른쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2 + 1 힙 데이터 삽입 구현 # 힙 클래스 구현 class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) # 인덱스 1번부터 데이터가 삽입 # 삽입된 노드와 부모 노드 비교해서, 삽입된 노드가 위로 이동해야 하는지 결정 def move_up(self, inserted_idx): if in..

힙은 트리를 기반으로 하지만변형된 형태의 정책을 채택한다.힙(Heap)정의:데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)특징:힙을 이용해 최대값과 최솟값을 찾는 것은 O(logn)의 시간복잡도를 가짐 (cf. 배열 → `O(n)`)활용:우선순위 큐와 같이 최댓값이나 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용됨 힙의 구조분류최대 힙(Max Heap): 최댓값을 구하기 위한 구조최소 힙(Min Heap): 최소값을 구하기 위한 구조조건각 노드의 값은 해당 노드가 가진 자식 노드의 값보다 크거나 같음(최대 힙의 경우) → 루트 노드가 최댓값을 가짐완전 이진 트리의 형태(노드를 삽입할 때 왼쪽 노드부터 차례대로 삽입하는 이진트리) ..

** 이진 탐색 트리의 시간복잡도 트리의 높이(Depth)를 h라고 하면, 이진 탐색 트리의 시간복잡도는 O(h) n개의 노드를 가진다면, h = log(n) 에 가깝기 때문에, 시간복잡도는 O(log(n)) 동작을 한번 실행 할 때마다 가능한 선택지가 반으로 줄여지기 때문에, 실행시간 역시 반으로 단축시킬 수 있다는 것을 의미한다. ** 이진 탐색 트리의 단점 트리가 균형 잡혀 있을 경우, 평균 시간복잡도 O(log(n)) 최악의 경우, 링크드 리스트와 동일한 성능을 갖게 되고 시간복잡도는 O(n)

** 트리 노드 삭제 3가지 경우의 수를 나눠서 생각 1) Leaf 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드를 가리키지 않도록 한다 2) Child 노드가 1개인 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드의 Child 노드를 가리키도록 한다 3) Child 노드가 2개인 노드 삭제 시 - 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. or - 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. **파이썬 객체지향 프로그래밍으로 트리 구현 ---> (삽입), (탐색), 삭제 class BinarySearchTree: def __init__(self, head): s..

** 파이썬 객체지향 프로그래밍으로 트리 구현 ---> 삽입, 탐색, (삭제) 1) 노드 클래스 구현 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 2) 이진 탐색 트리 구현 class BinarySearchTree: def __init__(self, head): self.head = head # 삽입 def insert(self, value): self.current_node = self.head # 비교대상으로, 헤드부터 시작 while True: if value value: self.current_node = self.current_node.left # 이동 else: self.c..