CS/자료구조 (3) 썸네일형 리스트형 Hash Table & BST 1. BST는 어떤 자료구조 인가요? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다. 검색과 저장, 삭제의 시간복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 tree가 됐을 때 O(n)입니다. 2. 이진트리(Binary tree)는 어떤 자료구조 인가요? 모든 node의 child nodes의 갯수가 2 이하인 트리를 이진 트리라고 합니다. 3. BST의 worst case 시간.. Queue & Stack 1. Queue는 무슨 자료구조 인가요? queue는 선입선출 FIFO(First In First Out)의 자료구조입니다. 시간 복잡도는 enqueue O(1), dequeue O(1) 입니다. 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있습니다. 2. Array-Base 와 List-Base의 경우 어떤 차이가 있나요? Array-Base의 경우 queue는 circular queue로 구현하는 것이 일반적입니다. 이는 메모리를 효율적으로 사용하기 위함입니다. 또한, enqueue가 계속 발생하면 fixed size를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 합니다. 그럼에도 enqueue의 시간복잡도는 (amort.. Array & Linked List 1. Array는 어떤 자료구조 인가요? Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 입니다. 2. 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요? 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당합니다. 모든 데이터를 옮 겼다면 기존 Array는 메모리에서 삭제하면 됩니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 합니다. 3. Dynamic Array는 어떤 자료구조 인가요? Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추 가되면 저장할 수 없습니.. 이전 1 다음