bdfgdfg

그래프와 관련된 용어 위 그림과 같이 그래프에서는 정점(vertex)는 연결의 대상이 되는 개체 또는 위치. 간선은 그들 사이의 연결(다리)이다. 더 간단한 그림의 예시를 본다. 다음은 비상연락망 구조를 표현한 그래프. 위의 그래프에서는 방향성이 빠져있다. 이렇듯 그래프의 연결 관계에 있어서 방향성이 없는 그래프를 가리켜 '무방향 그래프'라고 한다. 그리고 위와 같이 간선에 방향정보가 포함되어 있으면 '방향 그래프' 가중치 그래프와 부분 그래프 다음 그림에서 보이듯 간선에 가중치 정보를 넣을 수 있다. 이러한 형태의 그래프를 가리켜 가중치 그래프라 표현한다. 이 때 가중치가 되는 값은 다양하게 설정할 수 있다. 예로들어 1. A정점에서 B정점까지 걸리는 '시간' 2. A정점에서 B정점까지 걸리는 '거리'..

충돌 문제의 해결책 일반적으로 충돌의 해결책이란 것이 상식적인 선에서 벗어나지 않는다고 한다. 예를 들어 충돌이 발생하면 충돌이 발생한 그 자리를 대신해 빈 자리를 찾아야 한다. 다만 그 빈 자리를 찾는 방법에 따라서 해결책이 구분될 뿐. 1. 선형 조사법과 이차 조사법 선형 조사법 - 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 '선형 조사법' 예를 들어 밑의 그림과 같이 key % 7의 해시값을 구하는 해시 함수가 있다. 1. 키가 9인 데이터는 해시 값이 2(9 % 7 -> 2)이므로 인덱스 2에 저장이 된다. 2. 이어서 키가 2인 데이터가 등장. 2 % 7 -> 2이므로 인덱스 2에 저장이 할려하지만 이미 9가 저장이 되었기에 충돌! 3. ..

해시 테이블 탐색에 있어 매우 빠른 결과를 보여주는 자료구조이다. -> 탐색의 시간 복잡도는 O(1). 즉 내가 찾고자 하는 대상을 한번에 찾아내는 방식. C++에서도 STL 컨테이너에서 제공하는 해시테이블이 존재한다. -> std::unordered_map(Key-Value), std::unordered_set(Key) 참고로 앞서 배운 이진 탐색 트리의 컨테이너는 std::map(Key-Value) 테이블(Table) 위 그림이 테이블. 자료구조 관점에서 위 그림 처럼 저장되는 데이터가 키(key)와 값(value)이 하나의 쌍을 이뤄야 테이블이라 한다. 그렇기에 테이블에 저장되는 모든 데이터들은 이를 구분하는 '키'가 있어야 데이터를 구분하는 기준이 된다. 그렇기에 테이블은 키와 관련해 다음과 같은..

보완된(균형 잡힌)이진 탐색 트리의 구현 기존에 구현 했던 이진 탐색 트리에 추가적으로 구현을 한다. 리밸런싱 관련된 기능 추가와 BSTInsert 메소드와 BSTRemove 메소드를 수정. 먼저 리밸런싱에 필요한 도구들을 정의한다. 1. 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이를 구하여 불균형 여부를 판단하기 위한 함수. -> int GetHeight(Node* bst) template int BinarySearchTree::GetHeight(Node* bst) { int leftH; // left 높이 int rightH; // right 높이 if (bst == nullptr) return 0; // nullptr을 반환하므로 int형으로 형변환. leftH = GetHeight(bst->..