CS 지식/자료구조3 [자료구조] 해시테이블 🗄️ 해시 테이블이란? 해시 테이블(hash table)이란 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 즉, 키를 사용하여 그 키에 해당하는 값을 찾기 위해 필요한, 빠른 속도로 키를 검색할 수 있는 자료 구조를 의미한다. 그림 자료를 바탕으로 다시 이해하면, 해시 테이블은 데이터를 저장하는 일종의 자료구조이다. 예를 들어 각 사람의 전화번호를 저장하고자 할 때,각 사람의 이름을 키(key) 값으로 사용하고 해당 사람의 전화번호는 키와 매칭되는 공간에 적재한다.이 때 키를 인덱스로 사용하기 위해 해시 함수(hash function)를 거쳐 인덱스로 만드는 과정이 추가되는 것이다. 해시 함수를 왜 사용할까? 여기서 사용하는 키 값은 문자열이 될 수.. 2024. 10. 27. [자료구조] 이진탐색트리(Binary Search Tree) 이진탐색트리란?이진탐색트리는 이진트리의 한 형태로, 특정 규칙을 따르는 노드들로 이루어진 트리이다. 각 노드에는 값이 저장되고, 다음과 같은 속성을 가진다.각 노드에 중복되지 않는 키(key)가 있다. 왼쪽 서브트리의 모든 노드는 루트 노드보다 작은 값을 가진다.오른쪽 서브트리의 모든 노드는 루트 노드보다 큰 값을 가진다. 좌우 서브 트리도 모두 이진 탐색 트리(자식 노드가 최대 2개인 트리)여야 한다. 이 속성 덕분에 효율적인 탐색, 삽입, 삭제 연산이 가능하다. 주요 연산탐색(Search): 원하는 값을 찾을 때, 루트 노드에서 시작하여 값을 비교하며 왼쪽 또는 오른쪽으로 이동한다. 탐색의 시간 복잡도는 트리의 높이에 따라 O(h)가 된다. 삽입(Insertion): 새로운 노드를 삽입할 때도 루트부.. 2024. 9. 6. [자료구조] 큐(Queue)와 스택(Stack) 큐(Queue)란?큐 자료구조는 대표적인 선입선출(First In First Out; FIFO)의 자료구조다. 대기열이라고도 하는데, 표 같은 것을 구매하기 위해 줄을 서는 것을 의미한다.가정 먼저 줄을 선 사람(First In)이 가장 먼저 표를 구매하고 가장 먼저 매표소를 빠져나가는 것(First Out)이다. 큐의 연산enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부dequeue : 큐 맨 앞쪽의 요소를 삭제peek : front에 위치한 데이터 읽음front : 큐의 맨 앞의 위치(인덱스)rear : 큐의 맨 뒤의 위치(인덱스)isFull : 큐가 꽉 찼는지 확인. rear == n - 1 즉, r.. 2024. 7. 16. 이전 1 다음
