배움 저장소

트리와 달리 그래프는 한 정점(Vertex)가 여러 다른 정점을 가리킬 수 있다 그래프는 두 정점이 서로를 가르킬 수 있다 연결된 상태를 간선(Edge)으로 표시한다 인접 행렬(Adjacent Matrix Graph) 인접행렬은 정점간 연결관계를 행렬로 표시한다 2차원 배열을 사용하여 정점의 연결 관계를 나타낸다. X행의 X 정점과 다른 정점과 연결 여부를 표시한다 인접 행렬로 그래프 그리기 https://graphonline.ru/en/create_graph_by_matrix visited_ 값은 traversal을 확인할 때 사용한다. 깊이 우선 탐색(Depth First Search) 방문한 정점을 깊이 파고든다 스택을 활용한다 너비 우선 탐색(Breadth First Search) 중심이 되는 정..

보간탐색 인덱스와 값의 크기는 비례하다고 가정 작은 값은 작은 인덱스부터 탐색한다. 큰 값은 큰 인덱스부터 탐색한다 첫 값부터 마지막 값 사이의 길이 : 첫 값부터 x값까지 길이 = 인덱스 길이 : Position 길이 (arr[high] - arr[low]) : (x - arr[low]) = (high - low) : (pos - low) 이 때 버림을 활용하여 index 값이 int InterpolationSearch(int arr[], int low, int high, int x) { rec_count++; if (low = arr[low] && x x) return InterpolationSearch(arr, low, pos - 1, x); } return -1; } 색인 순차 탐색 원 배열을 각..

쉘 정렬 Insertion Sort는 바로 옆 값을 값을 비교하고 정렬한다. Shell Sort는 멀리 있는 값을 비교하고 정렬하여 효율을 얻는다. 성능 Worst : O(n^2) Average : O(n^1.5) 구현하기 void ShellSort(int arr[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { cout

이진탐색트리 시간복잡도 균형잡힌 트리: O(Log N) Worst : O(N) 이진 탐색 트리의 한계 완전 이진 트리가 아니므로 비효율적으로 작동할 수 있다 역순으로 정렬된 배열 값을 모두 넣을 경우 양 서브트리의 깊이가 비슷할 때 효율적이다 구현하기 IterGet Item* IterGet(const K& key) { Node* cur = root_; while (cur) { if (cur->left && key item.key) cur = cur->left; else if (cur->right && cur->item.key right; else // handle two case (cur->item == key) & (empty child, No matchin..

최대 힙(Max Heap)과 Top에서 최대값을 출력한다. 최소 힙(Min Heap) Top에서 최소값을 출력한다. 보관된 값은 정렬되어있지 않다. 트리 개념을 활용하여 배열로 구현한다. 최대값 혹은 최소값을 매 번 꺼낼 때 유리한 자료구조이다. 최대 힙(Max Heap) 1. 구현원리 완전 이진 트리를 항상 유지한다 Root 값은 항상 최대값이다 2. 값 저장하기 따라서 값을 추가할 때 완전 이진 트리를 유지할 수 있는, 왼쪽에서 비어있는 순서대로 값을 대입한다 대입될 노드와 해당 노드의 부모를 비교한다 대입될 노드가 부모보다 크다면 자리를 바꾼다(Root까지 반복진행한다) 항상 자식이 부모보다 작다 Swap이 아닌 Shift를 쓰자(새로 만든 노드는 완전 이진 트리를 만들 수 있는 자리에 넣지 않고 ..

선형 vs 비선형 자료구조(Linear/ Non-Linear) 선형 자료구조 데이터 모두가 연결된 상태로 구현한다(직선으로 표현할 수 있다) 리스트(List), 스택(Stack), 큐(Queue) 위 자료구조를 배열 또는 연결노드로 구현할 수 있다. 비선형 자료구조 데이터 모두가 연결되지 않은 상태이다(직선으로 표현할 수 없다) 트리(Tree), 그래프(Graph) 이진 트리 소개 양방향 연결 리스트와 이진 트리 모두 Left와 Right 노드 포인터를 사용하지만 이진 트리는 자식-부모 관계를 다룬다. Root Node : 트리의 시작점으로 부모가 없다. Terminal{Leaf} Node(단말노드): 자식이 없는 노드 Edge : 노드와 노드의 연결을 가리킨다. Degree(차수) : 자식의 개수 Tr..

Node* current = first_; while(current->next) { current = current->next; } 순차 표현 vs 연결 표현 Sequential Representation 장점 : 데이터를 묶음별로 다룰 수 있어 효율적이다. 단점 : 중간에 데이터를 삽입하거나 제거하면, 그 뒤의 데이터를 이동시켜야 한다. 따라서 Sequential Representation은 많은 데이터를 읽어들이는데 유리하다 데이터를 연속적인 데이터 중간에 추가하거나 제거하는데 불리하다 Linked Representation 장점 : 중간에 데이터를 삽입하거나 제거하는 일이 빠르다. 단점 : 다음 Node에 접근하기 위해 이전에 존재하는 모든 Node를 거쳐야하므로 비효율적이다. 데이터를 삽입하거나 ..

원형 큐 FIFO(First in First Out) 원형 큐에서 두 개의 index를 활용하여 비어있을 경우, 1개 있을 경우, 2개 있을경우, ..., 꽉 차있을 경우를 표현해야 한다. 모든 경우를 각각 유일하게 표현할 수 있도록 index를 사용하는 방법은 무엇인가? front는 시작 index보다 1 작은 값을 가진다. rear는 가장 마지막에 추가된 index이다. front == rear일 때 원형 큐는 비어있다. 위 규칙을 적용하고 capacity -1 개의 저장공간만 사용한다(front가 가리키는 곳은 항상 비어있다) 원형 큐의 구현 원리 front와 rear 모두 0 index에서 시작한다. 값을 추가하면 rear를 증가시켜 해당 index에 값을 할당한다 값을 뺄 때 front 값을 증..