자료구조

해시 테이블이란? hash table은 key를 value에 매핑할 수 있는 자료구조로서 효율적인 탐색(빠른 탐색)을 할수 있게 해준다. 해시함수에 key값을 입력으로 넣어 얻은 해시값을 인덱싱하여 저장한다. 해시 함수란? 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말하며 MD4, MD5, SHA등이 있다. 다양한 해싱 알고리즘이 있지만 가장 단순하면서도 널리 쓰이는 알고리즘으로는 정수형 해싱 기법인 모듈러 연산을 이용한 나눗셈 방식이 있다. 수식은 다음과 같이 정리할 수 있다. h(x)= x mod m 여기서 h(x)는 입력값 x의 해시 함수를 통해 생성된 결과로 m은 해시 테이블의 크기이며 일반적으로 소수를 선택하는 것이 좋다. 해시 함수 알고리즘은 이정도로 하고 넘어가..

이진탐색트리 BST(Binary Search Tree)란?? 이진탐색트리는 정렬된 트리이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있으며 저장과 동시에 정렬을 하는 자료구조이다. 검색과 저장, 삭제의 시간복잡도는 모두 O(log n)이고, worst case는 한쪽으로 치우친 트리가 됐을때 O(n)이다. (시간복잡도란?? click!) 이진탐색트리(BST)의 조건 root node의 값보다 작은 값은 왼쪽 subtree에, 큰 값은 오른쪽 subtree에 있다. subtree도 1번 조건을 만족한다.(Recursive) 이진트리(Binary tree..

스택이란?? stack은 후입선출 LIFO(Last In First Out)의 자료구조이다. 시간복잡도는 push O(1), pop O(1)이다. (시간복잡도란?? click!) 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로가기), 깊이 우선탐색(DFS)이 있다. push: stack에서 데이터를 추가하는 것을 말한다. stack의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)이다. pop: stack에서 데이터를 추출하는 것을 말한다. push와 동일하게 pop의 경우도 맨 뒤에 데이터를 삭제하면 완료되기 때문에 O(1)의 시간복잡도를 갖는다. push, pop 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 구현된다. 관련 알고리즘 문제..

Queue란?? 큐는 선입선출 FIFO(First In First Out)의 자료구조이다. 시간복잡도는 enqueue O(1), dequeue O(1)이다. 활용 예시는 캐시구현, 프로세스 관리, 너비우선탐색(BFS)가 있다. (캐시란?? click!) (프로세스란?? click!) FIFO Queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입 선출 FIFO형식으로 데이터를 저장하는 자료구조이다. enqueue & dequeue 큐에서 데이터를 추가하는 것을 enqueue라고 한다. 큐에서 데이터를 추출 하는 것은 dequeue라고 한다. euqueue의 경우 큐의 맨 뒤에서 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)이고 이와 비슷하게 dequeue의 경우 맨 앞의 데이터를 삭..

Index란?? index는 데이터베이스에서 table의 검색 성능을 높여주는 자료구조를 말한다. 일반적인 RDBMS에서는 B+Tree 구조로 된 index를 사용하여 검색속도를 향상 시킨다. 책마다 마지막 페이지에 있는 색인과 같은 역할을 하는 자료구조이다. 책에서 어떤 용어나 단어를 찾기 위해 첫 페이지부터 끝까지 전체를 훑지 않아도(Full table scan) index를 찾아보면 몇 페이지에 적혀 있는지 바로 찾을 수 있는 것과 비슷한 개념이다. index 구조 index는 Btree, B+tree, Hash, Bitmap으로 구현될 수 있다. 많은 데이터베이스 시스템에서 index는 B+tree구조를 가진다. index를 생성하게 되면 특정 column(속성, attribute)의 값을 기준으..

array란? array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다. array의 특징 고정된 저장 공간 순차적인 데이터 저장 array의 장점 lookup과 append가 빠르다. 따라서 조회를 자주 해야되는 작업에서 array자료구조를 많이 쓴다. array의 단점 fixed-size의 특성상 선언시에 array의 크기를 미리 정해야 하므로 메모리의 낭비나 추가적인overhead가 발생할 수 있다. 만약 미리 예상한 것보다 더 많은 수의 data를 저장하느라 array의 size를 넘어서게 된다면?? 기존의 size보다 더 큰 array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 array는 메모리에서 삭제한다. 이런식으로 동적..