개념 해시 함수를 이용하여 키(key)를 index로 만들어 배열의 해당 index에 데이터를 보관하는 자료구조 보통 키(key)로 값(value)을 맵핑하는 식으로 사용한다. C++ STL의 unordered_map, unordered_set, 그리고 여러 언어들의 Dictionary나 HashMap, HashSet 등이 포함된다. 특징 - 배열의 각 요소는 키와 값 등으로 이루어진 구조체(및 클래스)로 이루어져 있다. - key를 index로 변환시키는 다양한 해시 함수가 존재하며, 이의 성능에 따라 더욱 성능이 좋아질 수 있다. - 특정 요소 삽입, 삭제, 탐색이 O(1)이며, 최악의 경우 O(N)이다. 장점 특정 요소를 탐색할 때 O(1)으로 굉장히 빠르다. 단점 1. 충돌 가능성을 줄이기 위해 ..

개념 각각의 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지고 있는 이진 트리 구조다. 데이터를 삽입할 때, 각각의 노드와 비교하며 삽입할 데이터가 노드의 데이터보다 작을 시 왼쪽 자식으로, 클 시 오른쪽 자식으로 내려가며 비어있는 곳까지 내려가 삽입된다. 특징 1. 트리에서 데이터를 검색할 때 이진 탐색 알고리즘과 동일한 시간 복잡도의 성능을 가진다. 2. 중위 순회로 데이터들을 정렬된 상태로 순회할 수 있다. 3. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 4. 요소의 삽입, 삭제, 접근은 O(logN), 최악의 경우 O(N) 이다. 장점 1. 특정 데이터를 검색할 때 꽤나 빠른 편이다. O(logN)..

개념 덱은 양방향 큐 (Double Ended Queue)의 줄임말이다. 이름 그대로 큐 구조가 양방향으로 되어있다. 즉, 데이터의 삽입, 삭제가 맨 앞과 맨 뒤에서 이루어지는 구조다. (큐는 먼저 추가한 데이터부터 삭제하는 구조, 선입 선출) 한글 발음으로 덱, 데크로 불린다. 특징 1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다. 3. 요소의 삽입은 맨 앞, 맨 뒤에 삽입할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다. 요소의 삭제는 맨 앞, 맨 뒤를 삭제할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다...

개념 가변 배열이라고도 불리며, 크기가 고정되어 있지 않은 배열이다. 배열을 조금 더 쉽고 활용도 높게 사용하기 위한 자료구조다. C++ STL에서의 vector, Java에서의 ArrayList 등이 해당된다. 특징 1. 배열이기 때문에 메모리가 연속적이다. 2. 일반 배열과는 다르게 배열의 데이터가 용량보다 많아지는 순간 배열을 더욱 크게 재할당 한다. 3. 일반 배열과는 다르게 중간에 데이터 삽입이 가능하며 데이터 손실이 없다. 4. 일반 배열과는 다르게 중간의 데이터 삭제가 일어날 경우, 빈 공간 없이 한 칸씩 당겨진다. 5. 요소의 삽입은 맨 뒤에 삽입할 경우 O(1), 이외에는 O(N) 이며 요소의 삭제는 맨 뒤를 삭제할 경우 O(1), 이외에는 O(N) 이다. 특정 원소 접근은 O(1) 이다..

개념 연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료 구조이다. 특징 - 연결 리스트는 맨 처음 삽입한 노드의 주소를 가지고 있다. - 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있다. - 데이터가 추가될 때마다 새로 노드를 할당하기 때문에 노드끼리의 메모리는 불연속적이다. - 요소의 삽입와 삭제는 O(1) 이며, 특정 원소 접근은 O(n) 이다. 장점 1. 동적인 크기의 데이터를 다루기에 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다. - 일반 배열은 크기를 늘릴 수 없음 - 동적 배열(vector, ArrayList 등)은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(N) 2. 각 요소 사이에 데이터를 추가하더라도 O(1) 로 굉장히 빠르다. - 일반 배열과 동..