자료구조

Search, Insert, Delete를 모두 상수시간에 하는 것이 목표다!가능할까?➡️ key 값 비교를 하지 말고 key 값으로 자리를 정하자! Hashing Methoddivsion hashing - h(k; p) : k mod p (p는 소수이고 table size와 비슷하면서 작은 숫자 주로 2의 거듭제곱)근데 2의 거듭제곱을 divisor로 사용했을 때 문제점: $2^3$로 하면 하위 3개 digit들만 영향을 받음 그럼!multiplicative hashing - $h(k; a) =  \left \lfloor (a\times k \times mod W)/(W/M)\right \rfloor$a는 보통 W에 대한 소수로 정함근데 만약에 $W=2^w$이고 $M=2^M$이면...? - right ..

GraphG = (V, E)V : node/vertices의 집합E : edge/link의 집합undirected graph - 방향이 없음 (E를 집합으로 나타냄 {A, B} )N(v) - v의 주변 노드의 집합deg(v) = |N(v)| 주변 노드의 수directed graph - 방향이 있음 (E를 순서쌍으로 나타냄 (A, B) 랑 (B, A)는 다름 )u->v , u$N^{-}(v)$ v로 들어오는 노드$N^{+}(v)$ v로 나가는 노드$deg^{-}(v)$ 들어오는 노드의 수 in-degree$deg^{+}(v)$ 나가는 노드의 수 out-degreeVarious Graphssimple graphmultigraph - 두 노드를 잇는 edge가 여러 개pseudograph - multigrap..

만약에 data가 외부 disk에 저장되면 어떡하지.. 한번 접근하는 데 엄청 느릴 텐데..최대한 wide 하면서도 (depth가 적을수록 좋다는 뜻) 한 disk block에 fit 할 수 있어야 함 B tree의 조건 : 임의의 k (keys)에 대하여 - floor 한 node 수k'개의 key를 갖고 있는 non-leaf node는 k' + 1개의 children이 있다. $T_{0} node 안에는 적 어 도 $\left \lfloor k/2\right \rfloor \leq k' \leq k$모든 leaf node들이 같은 층에 있어야 함B tree의 조건 : 임의의 m ( children)에 대하여 - ceiling 한 node 수m개의 children을 갖고 있는 non-leaf node는..

배웠으나 까먹고 또 배웠으나 헷갈리는 그래서 정리해 둬야겠다.이미 배웠던 분들이 복기하는 용도로 사용하면 좋을 것 같다. 시간 복잡도 ⍬(n2 )[정렬되지 않은 리스트의 크기를 n부터 시작해 하나씩 줄임]Selection sort( 선택 정렬 ) : 제일 큰(작은) 수를 찾아서 제일 뒤(앞)로 보내기코드보기def selectionSort(A): for i in range(0, len(A)-1): min_num = i for j in range(i + 1, len(A)): if A[j] Bubble sort( 버블 정렬 ) : 2개씩 비교해 가면서 큰 수가 점점 뒤로 가게 하기코드보기def bubbleSort(A): for i in range(len(..