본문 바로가기

자료구조7

[Javascript] 자료구조 - Hash Table 1. 해시 테이블(Hash Table)이란? 해시 테이블은 key와 value의 쌍으로 데이터를 저장하는 자료구조이다. 해시 테이블은 보통 배열을 기반으로 하며, 각각의 키에 대해 고유한 해시 함수를 사용하여 인덱스로 변환한 후 해당 인덱스에 값을 저장해서 빠른 데이터 검색 및 삽입을 가능하게 한다. 해시 테이블은 해시 함수를 사용하여 키를 인덱스로 변환하므로 데이터를 빠르게 검색하고 삽입할 수 있는데 해시 함수의 시간 복잡도가 O(1)에 가까울 경우에 검색 및 삽입 연산의 평균 시간 복잡도도 O(1)에 가깝다. 해시 테이블의 각 키는 해시 함수를 통해 고유한 인덱스로 변환된다. 이로 인해 중복된 키가 발생할 수 없으며, 각 키는 하나의 값과 연결된다. 가끔 해시 테이블의 문제로 해시 충돌이라는 상황이 .. 2024. 4. 2.
[Javascript] 자료구조 - Heap 1. Heap이란? 힙(Heap)은 자료구조의 한 종류로, 특정한 규칙을 가지는 이진 트리이다. 주로 우선순위 큐를 구현하는 데 사용된다. 힙은 완전 이진 트리의 일종으로 마지막 레벨을 제외한 모든 레벨에서 노드들이 완전히 채워져있고, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워져있다. 힙의 각 노드는 일반적으로 부모 노드보다 더 높은 우선순위를 가지고 있다. 이를 최대 힙(Max Heap)이라고 한다. 반대로 각 노드는 부모 노드보다 더 낮은 우선순위를 가지고 있는데 이를 최소 힙(Min Heap)이라고 한다. 힙은 부모노드와 자식노드간의 우선순위 조건이 항상 유지되어야한다. 따라서 삽입이나 삭제연산을 할 때 힙속성을 유지해야한다. 최대힙에서는 최대값을 빠르게 찾아야하며, 최소힙에서는 최소값을 빠르게.. 2024. 4. 2.
[Javascript] 자료구조 - 우선순위 큐 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 자료구조의 일종으로, 각 요소에 우선순위를 할당하고, 우선순위가 높은 요소가 먼저 처리되는 자료구조이다. 보통 큐(Queue)와 유사한 동작을 하지만, 일반적인 큐와 달리 요소를 꺼낼 때에는 해당 요소의 우선순위에 따라 선택된다. 우선순위 큐는 각 요소가 우선순위를 갖고 있으며, 이 우선순위에 따라 요소의 처리 순서가 결정된다. 일반적으로 우선순위가 높은 값이 먼저 처리된다. 이는 일반적인 큐의 형태를 가지고 있으나, 요소의 처리는 우선순위에 따라 이루어진다. 힙이나 이진 검색 트리와 같은 자료구조를 사용하여 구현된다. 힙은 우선순위 큐를 구현하는 데 가장 효율적이며, 삽입, 삭제, 우선순위 변경 등의 연산을 빠르게 수행할 수 있다. 2... 2024. 4. 1.
[Javascript] 자료구조 - Tree 1. Tree란? 자료구조에서 Tree(트리)는 계층적인 구조를 나타내는 비선형 자료구조이다. 트리는 노드(Node)들로 이루어져 있으며, 노드들은 간선(Edge)으로 연결되어 있다. 트리에서는 각 노드가 부모(Parent)와 자식(Child) 노드로 구성된다. 트리 구조에서 맨 위에 있는 노드는 루트노드라고 하며, 아래로 내려가면서 다양한 노드들이 연결되어 있다. 각 노드는 자신의 부모 노드와 연결된 간선을 통해 상위 레벨의 노드에 접근할 수 있다. 2. Tree가 사용되는 사례 트리는 여러 용도로 활용되는데 예를 들어, 데이터베이스에서 인덱싱(indexing), 파일 시스템의 폴더 구조, 컴퓨터 네트워크의 라우팅 테이블 등에서 사용된다. 또한 알고리즘에서는 이진 트리(Binary Tree), 이진 .. 2024. 3. 29.
[Javascript] 자료구조 - Linked List 1. Linked List란? Linked List란 선형의 자료구조인데, 데이터 요소들을 순서대로 저장하는데 사용된다. 각 요소들은 데이터와 다음 요소를 가리키는 포인터로 이루어져있다. 다음 요소의 정보가 있기 때문에 이 포인터 정보를 통해서 연결되어있는 연결 리스트인 것이다. 그렇기 때문에 메모리에 연속적으로 저장이 되지 않아도 된다. 2. Linked List가 사용되는 사례 Linked List는 다양한 분야에서 사용이 되는데 데이터 요소를 순차적으로 저장하여 효율적인 삽입 및 삭제를 가능하게 하기 때문에 스택과 큐와 같은 추상 자료형을 구현할 때도 활용되며, 후입선출과 선입선출 데이터 구조를 각각 지원한다. 또한 동적 메모리 할당을 위한 메모리 관리에 사용되며, 그래프 및 트리 알고리즘에서는 .. 2024. 3. 29.
[Javascript] 자료구조 - Queue 1. Queue란? Queue도 자료구조의 한 종류인데, Queue는 먼저 들어온 데이터가 먼저 나가는, 선입선출의 구조를 갖고 있다. 대기열, 줄 서는 것과 같은 개념을 자료구조로 구현한 것이다. Queue를 다룰 때 기본적인 기능으로 enqueue(데이터 삽입), dequeue(데이터 제거, 반환), peek 또는 front(Queue의 가장 앞에 있는 항목 반환) 등이 있다. 2. Queue가 사용되는 사례 이러한 자료구조적 특성을 바탕으로 Queue는 여러가지 상황에서 사용되는데, 주로 대기열관리, 프로세스 스케줄링, 네트워크 패킷 처리, 프린터 대기열, 이벤트 처리, 멀티스레드 환경에서의 작업 처리 등 요청을 순차적으로 처리하는 경우에 주로 사용된다. 3. Javascript로 구현한 Queue.. 2024. 3. 28.

티스토리툴바