구프의 메모장

종류 1. AVL Tree (트리에서 설명함) 2. B-Tree ( Bayer & McCreight , 1972 ) 이진트리, 2-3트리, 2-3-4트리 등을 일반화 시킨 트리로, 현재까지도 계속 알고리즘이 업그레이드 되고 있음. 2-1. 정의 모든 노드가 좌에서 우로갈수록 증가하는 k개의 데이터를 가짐. ( 이때, 데이터의 개수 k는 n의 절반 이상, n 이하 ) - n = 1, (0

기존 검색 시간은 O(lg N) 인데, 이것을 O(1)로 낮추기 위한 시도 -> 배열의 크기, 데이터 량에 관계 없이 검색의 시간이 동일하게 함. 방법 : 매우 큰 공간을 가진 Hash table를 만든다. 이때 hash table의 사이즈 M은 소수이다. (Prime number) 공간낭비가 커 효율이 떨어지지만 긴급한 검색의 경우 필요해 만들어짐. 1. 배경 data K가 저장될 위치를 data K를 통해 구하는 방식 h(K) : Hash function, Table[h(k)] = k로 저장 2. 문제점 2-1) 충돌 (Collision) 서로 다른 데이터 X, Y에서, h(X) == h(Y)가 돼버리는 경우 ( 서로 다른 데이터가 같은 해시를 지님 ) 2-2) 군집화 (Clustering) 데이터가..

G=(V, E) | V는 정점(Vertice), E는 간선(=Edges) Node a, Node b = Vertice // line(a,b) = Edge G`=(V`, E`)에서 (V`,E`)가 (V, E)에 포함되면 이것은 G(V, E)의 subGraph(부분 그래프)이다. Edge에 방향이 없다면 : 무향 그래프 (Undirected Graph) Edge에 방향이 있다면 : 유향 그래프 (Directed Graph, =Di Graph) Edge에 Weight가 있다면 : 가중치 그래프 (Weighted Graph) 정점 B가 정점 A에 인접해 있다면 : 인접 정점 (Adjacent Vertex) 정점 B의 인접 정점의 수 : 차수 (Degree), 방향이 있는 경우 in-degree / out-deg..

배열 A[1...N]의 N개 데이터를 Sort하는 가장 빠른 방법? - 비교기반 정렬 (Comparison based Sorting) = Ω(N lgN) - 선택정렬, 삽입정렬, 버블정렬 -> O(N^2) - 쉘 정렬 -> O(N√N) / 최악 : O(N^2) - 합병 정렬, 퀵 정렬, 힙 정렬, BST -> O(N lgN) - 기수 정렬 -> O(N) [비교기반 정렬이 아님] 1. 선택 정렬 (Selection Sort) 전체를 탐색한 후, 최소or최대값을 왼쪽으로 이동시킴 - 왼쪽부터 차례로 검사하면서 가장 큰 수를 가장 왼쪽으로 이동 - 가장 왼쪽은 반복할때마다 한 칸씩 오른쪽으로 당겨짐 정상적으로 정렬된 것을 확인할 수 있음. 2. 삽입 정렬 (Insertion Sort) 뒤에서 시작해서 앞으로 ..

Heap : 완전 이진트리, 배열 H[1...N]에 저장됨. Heap의 성질 : P >= L,R (Max heap) or P Heap이 위에서 아래로 확장 // O(N lgN) 3-2) Bottom-up(상향식) 구성 - 모든 단말 노드를 Heap으로 구성한 후, N/2 ~ 1 까지 차례대로 추가함 (HeapDown을 N/2번 반복) => Heap이 아래에서 위로 확장 // O(N) 3-3) 상향식이 하향식보다 빠른 이유 하향식 : 1*0 + 2*1 + 2^2*2... 이렇게 변수가 같이 올라감 상향식 : 1*h + 2*(h-1) + 2^2*(h-2)... 이렇게 한쪽은 올라가고 한쪽은 내려감.

Tree는 나무 줄기가 갈라지듯이 Root노드에서부터 노드들이 퍼져나가는 방식의 자료구조이다. 트리는 Graph의 한 종류이며, Connected(모두 연결됨), Acyclic(비순환)의 성격을 갖는다. G(V, E)로 표현하며, V는 Set of Vertices(노드 구조체), E는 Set of Edges(노드 사이의 연결선)을 의미한다. 트리의 가장 밑에 있는 노드를 단말 노드라고 하며, Root부터 단말노드까지 내려가는데 거치는 노드의 수를 Level이라한다. 가장 Level이 높은 Node의 level이 Height가 된다. (노드의 높이) 1. K-ary Tree (K진 트리) 모든 노드의 자식이 k개 이하인 트리를 K진트리라고한다. 2. 이진 트리 (Binary Tree, BT) 모든 노드의 ..

Queue 는 First In-First Out(FIFO) 규칙이 지켜지는 자료 구조이다. 구현방식 1. SLL (Single-Linked List) - 그냥 SLL 2. Linear Array - 그냥 선형 배열 문제점 : 제한된 공간 내에서 data가 한 쪽으로만 이동하므로 한계에 도달하면 Drifting(표류)현상이 일어날 수 있음. 해결법 : Circular Array 사용 3. Circular Array Head - Output data (초기 key : 0) / Tail - Input data (초기 key : 0) 문제점 : 삽입, 삭제를 아무리 해도 Head와 Tail의 key값이 똑같음. 해결법 : - 1) Counter 도입. (FULL : Count = n) (EMPTY : Count..