흰 스타렉스에서 내가 내리지

# Trie 란? - 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다. - 검색할 때의 자동완성 기능, 사전 검색 등 문자열을 탐색하는 데 특화되어 있는 자료구조이다. - retrieval tree 가 어원이며, radix tree, prefix tree 라고도 불린다. # 장단점 - 문자열 검색을 빠르게 한다. - 문자열 탐색을 할 때, 전부 비교하는 것보다 시간복잡도 측면에서 훨씬 더 효율적이다. - 각 노드에서 자식들에 대한 포인터들을 모두 저장하고 있다는 점에서, 메모리 측면에서는 비효율적이다. # 예제 1. 'abc' 에 삽입 초기에 트라이 자료구조 내에는 아무것도 없으므로 Head의 자식노드에 'a'를 추가해준다. 'a' 노드에도 현재 자식이 하나도 없으므로, 'a'의 자식노..

힙(heap)은 내부 표현이 동적 배열이며 완전 이진 트리이다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 최대 힙 (max heap) : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 최소 힙 (min heap) : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 힙 트리 힙 트리의 특징 index(left_child) = index(parent) * 2 index(left_child) = index(parent) * 2 + 1 Max Heap 소스코드 class Element: def __init__(self, key): self.key = key class MaxHeap: # 이 곳에서는 힙의 크기를 최대 100으로 제한하고 있지만, # 실제 구현에서는 힙이 가득..

탐색 (Search) 란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 자료구조 (Data Structure) 란 데이터를 표현하고 관리하고 처리하기 위한 구조이다. 그 중 스택과 큐는 자료구조의 기초개념이고, 다음의 두 핵심적인 함수로 구성된다. Push - 데이터 삽입 Pop - 데이터 삭제

이진 탐색 트리의 정의 모든 키는 유일하다. 어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 서브트리의 그 어떤 키보다 크다. 어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 서브트리의 그 어떤 키 값보다 작다. (재귀적 정의) 노드의 서브트리도 이진탐색트리이다. 더 자세한 내용은 여기 Binary search tree - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Data structure in tree form sorted for fast lookup Binary search treeTypetreeInvented1960Invented byP.F. Windley, A.D. Booth, A.J.T..

전위 순회 (Preorder Traversal) def preorder(cur): if not cur: return print(cur.data, end=' ') preorder(cur.left) preorder(cur.right) 중위 순회 (Inorder Traversal) def inorder(cur): if not cur: return inorder(cur.left) print(cur.data, end=' ') inorder(cur.right) 후위 순회 (Postorder Traversal) def postorder(cur): if not cur: return postorder(cur.left) postorder(cur.right) print(cur.data, end=' ') 레벨 순서 순회 (L..

Queue class Queue: def __init__(self): self.container = list() def is_empty(self): if not self.container: return True else: return False def enqueue(self, data): self.container.append(data) # O(n) def dequeue(self): return self.container.pop(0) def peek(self): return self.container[0] 큐의 주요 특징 : FIFO (First In First Out) enqueue() 연산은 배열의 마지막에 원소를 추가하므로 시간복잡도가 O(1)인 반면, dequeue() 연산은 동적 배열의 첫 번째..

class Node: # 생성자 : 객체가 생성된 직후 반드시 호출됩니다. def __init__(self, data=None): self.__data = data self.__prev = None self.__next = None # 소멸자 : 객체가 사라지기 전 반드시 호출됩니다. # 삭제 연산 때 삭제되는 것을 확인하고자 작성. def __del__(self): print(f'data of {self.data} is deleted.') @property def data(self): return self.__data @data.setter def data(self, data): self.__data = data @property def prev(self): return self.__prev @prev..

class Stack: def __init__(self): self.container = list() def is_empty(self): if not self.container: return True else: return False def push(self, data): self.container.append(data) def pop(self): if self.is_empty(): return None return self.container.pop() def peek(self): if self.is_empty(): return None return self.container[-1] 주요 특징 : 맨 마지막에 들어온 데이터가 맨 처음 나간다. (LIFO, Last In First Out) 스택은 어디에 ..

삽입 및 삭제 조회 동적 배열 O(n) O(1) 연결 리스트 O(1) or O(n) O(n) 동적 배열에서의 데이터의 삽입과 삭제 데이터를 배열의 마지막에 추가하거나 삭제하는 경우, O(1). 하지만 배열이 가득 차 있을 때 (= 할당받은 메모리 공간을 다 채웠을 때), 충분한 공간을 다시 확보하고 기존 배열 요소를 모두 복사한 후 새로운 데이터를 추가한다. 데이터의 개수만큼 복사해야 하므로 이 때는 O(n)이다. 동적 배열에서 배열이 가득 찼을 때는 배열 크기의 2배만큼 메모리를 다시 잡는다. 반면, 배열의 중간에 원소를 삽입하거나 삭제하는 경우, 이미 있는 원소들은 모두 한 칸씩 밀리거나 당겨진다. 이에 최악의 경우 O(n)이 소요된다. 결론 : 배열의 마지막에 원소를 추가하거나 삭제하는 경우 O(1..

def sum(arr): total = 0 # 1 for a in arr: # 2 total += a # 3 return total #3 라인에서, CPU는 for문이 수행될 때 배열의 모든 원소를 가져오면서 항상 total값을 먼저 가져온다. 이처럼 한번 접근한 변수는 계속해서 접근할 가능성이 높다는 것이 시간 지역성(temporal locality)이다. # 2 라인에서, 다음에 접근할 배열의 원소는 이전에 접근한 원소의 바로 다음이다. 이처럼 이번에 접근할 배열의 원소는 이전에 접근할 변수 근처에 있을 가능성이 높다는 것이 공간 지역성(sptial locality) 이다. 이런 '지역성의 원리'로 인해 CPU와 메인 메모리 사이에 캐시를 두게 되었다. CPU 안에는 메인 메모리에서 가져온 데이터를 ..