mei 기술 블로그

1. 트리 (Tree) 계층적인 구조를 표현할 때 사용하는 자료구조 관련 용어 루트 노드 (root node) 부모가 없는 최상위 노드 단말 노드 (leaf node) 자식이 없는 노드 크기 (size) 트리에 포함된 모든 노드의 개수 깊이 (depth) 루트 노드부터의 거리 높이 (height) 깊이 중 최댓값 차수 (degree) 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 특징 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 부모 노드보다 왼쪽 자식 노드가 작음 부모 노드보다 오른쪽 자식 노드가 큼 예시 이진 탐색..

1. 우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용 구현 방법 단순 리스트 이용 힙(Heap) 이용 시간 복잡도 비교 구현 방법 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙(Heap) 정렬 단순히 N개의 데이터를 힙(Heap)에 넣었다가 모두 꺼내는 작업 시간 복잡도: O(NlogN) 2. 힙(Heap) 완전 이진 트리(Complete Binary Tree) 자료구조 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree) 항상 루트 노드(root node) 제거 최소 힙(min heap) 루..

1. 스택(Stack) 선입후출(FILO) 자료구조 먼저 들어온 데이터가 나중에 나가는 형식 구현 방법 Python: append(), pop() 메소드 사용 stack = [] stack.append(1) # 삽입 stack.append(2) # 삽입 stack.append(3) # 삽입 stack.append(4) # 삽입 stack.pop() # 삭제 print(stack[::-1]) # 최상단 원소부터 출력, [3, 2, 1] print(stack) # 최하단 원소부터 출력, [1, 2, 3]​ C++: stack 라이브러리 사용 (push() / pop() / top()) #include using namespace std; stack stack; int main(void) { stack.pus..