오뚝이개발자

Map(Dictinary)이란? value와 unique key가 mapping되는 자료구조 Ordered map vs. Unordered map ordered map : key값이 정렬된 것 - balanced tree로 구현 unordered map : key값이 정렬되지 않은 것 - hash table로 구현 Hashing이란? hash function을 통해 key value(hash key)를 table의 position으로 mapping시키는 것 Hash function을 고를 때 유의사항 계산에 드는 cost가 낮은 것(easy to compute) collision을 최소화하는 것 hash table slot에 데이터를 균등하게 분포시키는 것(evenly distributed) Hash에서..

Array란? 선형자료구조 + 모든 item 같은 자료형 + item들이 메모리 상의 countinuous하게 저장 Array의 문제점 특정 위치 insert, delete가 불편(모든 item 위치 재배치해야함) 만약 얼마나 많은 item을 저장해야 하는지 모르는 상황이면 최대한 많은 메모리를 할당해야 함(waste) Linked list란? data part + link part(다음 item의 주소 가리킴)로 구성 모든 item이 다음 item과 연결되어있는 item sequence array와 달리 메모리 상에 꼭 continuous하게 저장되지 않음(consecutive일수도 있고 아닐수도 있다) Linked list의 장단점 장점 삽입, 삭제가 array에 비해 쉽다 메모리 낭비 최소화(필요한..

Data structure란? 데이터를 효율적으로 사용하기 위해 데이터를 organizing하는 특정한 방법 용도에 따라 그에 적합한 data structure가 존재 Database -> B-trees Compile -> hash table 효과적인 Data structure를 고르는 방법 문제로부터 resource constraints(time, space)을 분석 필요한 basic operation을 결정 사용자의 요청이 어떠한 형태인지도 예시가 될 수 있다. 예컨대, exact-match query인지 아니면 range query인지 위 두 가지를 고려해 가장 잘 맞는 것을 선택한다. Data type이란? 다음의 네 가지를 결정하는 분류이다. 해당 type의 데이터가 가질 수 있는 value 해..