오뚝이개발자

Tree란? Connected, Acyclis, Undirected graph Tree는 Graph에 포함된다. Rooted tree란? 하나의 node가 root로 지정된 tree Tree에서 depth란? root 노드로부터 해당 노드까지의 edge 수 트리의 depth : lowest leaf의 depth(이것을 트리의 height라고도 한다.) Tree에서 level이란? depth와 비슷하지만 기준이 edge가 아닌 node 아래 그림에서 B, D는 각각 레벨이 2, 3인 노드이다. Binary tree란? 모든 node가 최대 2개의 child를 갖는 트리 Binary search tree(BST)란? x라는 key value를 갖는 노드의 left subtree에는 x보다 작은 값이, rig..

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에서..

Stack이란? LIFO(Last In First Out) order를 따르는 자료구조 예) 쌓여있는 책더미 Stack 구현의 두 가지 방법(item container로 어떤 것을 선택할지) Linked list로 구현(head에만 삽입하고 head만 지워 이를 stack의 top처럼 활용) Dynamic array로 구현(head를 포인터가 아닌 index 값으로 사용) Queue란? FIFO(First In First Out) order를 따르는 자료구조 예) 줄서기(waiting line) Queue 구현의 두 가지 방법 Linked list로 구현 Dynamic array로 구현 이 때, false-overflow 문제 발생 : 실제로는 빈 공간이 있는데 다 찬 것처럼 보이는 현상 그래서 나온 해..

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 해..