배움 저장소

트리와 달리 그래프는 한 정점(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..

문자열 ADT Data Type : 저장공간의 크기, 같은 Data Type의 연산을 정의한다. Abstract Data Type - 구현 하지 않은 Data Type. - 어떤 일을 해야하는 지 정의되어 있다. 예) class MyString { public: MyString(); // 비어 있는 MyString() 생성 MyString(const char* init); // 맨 뒤에 널 캐릭터'\0'가 들어 있는 문자열로부터 초기화 MyString(const MyString& str); // MyString의 다른 instance로부터 초기화 ~MyString(); bool IsEmpty(); bool IsEqual(const MyString& str); int Length(); void Resize..

재귀호출 재귀호출은 종료조건이 반드시 필요하다 가시화 도구 https://pythontutor.com/cpp.html#mode=edit - 가시화 도구에서는 함수 실행이 끝나면 stack 메모리 자체가 사라진다. 실제로는 우리가 프로그램을 실행시킬때 (OS가 프로세스를 만들어줄 때) 여유있는 크기의 stack 메모리를 미리 주고 편하게 사용하는 방식이다. - 함수 호출이 끝날 때 stack 메모리의 일부를 OS에게 반환하는 일은 없다(새 스택마다 메모리를 요청/반납하면 느려짐) - heap 메모리 공간은 매번 OS에게 요청하고 반납해야 합니다. 실행 위치에 따라 결과가 달라진다 void RecurFunc(int count) { if (count == 0) //