📌 Queue란? 큐(Queue): 데이터를 임시 저장하는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)구조이다. 스택(Stack): 큐와 같이 데이터를 임시 저장하는 자료구조로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO)구조이다. 큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 반대로 큐에서 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 큐에서 데이터를 넣는 쪽을 리어(rear)라 하고, 반대로 큐에서 데이터를 꺼내는 쪽을 프런트(front)라고 한다. 큐의 가장 큰 특징은 선입선출(FIFO)의 구조를 띄고 있다는 점과 너비 우선 탐색(BFS)에서 자주 사용된다는 점이다. 📌 OS scheduler와 Queue OS에서 프로세스를 스..

📌 이진 트리와 완전 이진 트리란? - 이진 트리(binary tree): 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 즉, 자식 노드가 최대 두 개인 노드들로 구성된 트리를 말한다. - 완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에 한해서 가장 왼쪽부터 오른쪽으로 노드가 채워져 있는 트리를 말한다. 📌 이진 검색 트리란? - 이진 검색 트리(binary search tree): 이진 검색 트리는 다음과 같은 조건을 갖는 이진 트리다. 왼쪽 서브트리 노드의 키 값은 노드의 키 값보다 작아야 한다. 오른쪽 서브트리 노드의 키 값은 노드의 키 값보다 커야 한다. 왼쪽 및 오른쪽 서브트리 노드도 각각 이진 검색 트리여야 한..

📌 해시 테이블이란? 해시 테이블(Hash Table): (key, value)로 데이터를 저장하는 자료구조다. 즉, key와 value가 1:1로 연관 되어 key를 통해 value를 도출할 수 있는 자료구조다. Hash Table은 마치 사전과 같다. 사전은 단어를 찾기 위해 사용되기보단, 단어의 정의를 찾기 위해 사용된다. Hash Table 또한 마찬가지이다. Hash Table에서 key는 단순히 value를 찾기 위한 수단이며, 결국 우리가 얻고자 하는 것은 value이다. 📌 해시 테이블 구성 - key: 임의 크기의 데이터 - hash function: 가변 길이의 값을(key) 고정 크기 값으로(hash) 매핑시켜주는 함수. - hash (=index): 고정된 크기의 값. - bucke..

📌 연결 리스트란? 연결 리스트는 데이터 요소의 선형 집합으로. 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다. 배열(Array)과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로, 다양한 ADT 구현의 기반이 된다. 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다. 데이터를 구조체로 묶어 포인터로 연결한다는 개념은 여러 가지 방법으로 활용이 가능하다. 📌 배열과 연결 리스트의 차이 연결리스트는 배열과 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미한다. 그래서 Linked list에서 가장 중요한 것은 '연결이 무엇인가'를 파악하는 것이다. 연결 리스트는 ..