Binary Search Tree Heap O(1)이 없지만 O(logn)은 가능 탐색은 O(n)이지만 나머지는 O(logn) *min/max는 빠름 정렬되어 있음 삽입이 쉽고 Priority Queue에 이용 크기변화에 유연함

배열이 데이터를 메모리에 연속으로 따닥따닥 보관했다면, 해시테이블은 메모리 이곳저곳에 랜덤으로 자료를 보관한다. 해시테이블은 언어에 따라 명칭이 다르지만, 모두 가지고 있는 중요한 자료구조다. 해시테이블은 key-value 쌍으로 이루어져 있는데, 여기서의 key는 배열에서 숫자 인덱스 역할을 한다. 배열은 데이터들이 0번칸부터 차례로 존재했기 때문에, 맨뒤 원소를 제외한 데이터의 추가/삭제를 하려면 인덱스 전체를 다시 싹 뜯어고쳐야하므로 O(n)의 시간이 소요됐다. 하지만 해시테이블은 key를 Hash Function에 넣어서 나온 해시를 메모리 주소로 하는 장소에 데이터를 보관하기 때문에, 주소의 중복만 일어나지 않는다면 O(1)의 시간복잡도를 가진다. 다시 말해, 같은 key값은 언제나 같은 해시를..

배열 : 연속된 메모리 공간에 같은 자료형의 데이터를 저장하는 방식. "인덱스"로 관리하기 때문에 다음과 같은 특징이 있다. 탐색 : 유리 O(1) 맨 마지막 위치에 삽입: 정적배열=>유리 O(1) / 동적배열에서메모리초과시=>불리 O(n) 맨 마지막 위치의 원소 삭제: 유리 O(1) 업데이트(원하는 위치에 삽입/삭제) : 불리 O(n) Static Array Dynamic Array 특징 배열을 정의할 때부터 길이를 정하기 때문에 고정됨 개발자가 메모리 관리할 수 있음 길이를 초과하게 되면 할당할 메모리를 새로 늘리고 이전 정보를 복붙해서 이어나감(보통 기존 크기의 2배로 옮김) 길이변화에 유연하지만, 메모리 관리에 소홀함 언어 저레벨 언어(C++) 고레벨 언어(Python-List, JS-Array,..