::public/자료구조11 그래프(Graph) 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용한다. 노드(Node) : 위치를 말한다. 정점(Vertex)이라고도 함. 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨.(link or branch) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 무방향 그래프 ; 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있음 보통 노드 A,B가 연결되어 있을 경우, (A, B) 또는 (B, A)로 표기 방향 그래프 ; 간선에 방향이 있는 그래프 보통 노드 A,B가 A->B로 가는 간선으로 연결되어 있을 경우, 로 표기. 는 B -> A로 가는 간선이 있을때에 표.. 2023. 8. 14. 해시 테이블 [참고] https://www.youtube.com/watch?time_continue=523&v=Vi0hauJemxA 2019. 10. 7. 해싱(hashing) / 해시테이블(hash table) / 해시함수(hash function) *해싱(hashing) ;키(key) 값을 해시 함수(hash function)라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용하여 바로 값(value)에 접근하게 할 수 하는 방법 _ *해시 테이블(hash table) ;해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조. -해시 테이블의 기본적인 연산은 삽입, 삭제, 탐색. *버킷(bucket) ;데이터가 저장되는 곳. 하나의 주소를 갖는 파일의 한 구역을 의미. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미함. *슬롯(slot) ;데이터가 저장되는 곳. 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형.. 2019. 9. 10. 그래프 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조. 정점(vertex)과 간선(edge)들의 집합으로 구성. 인접 정점(adjacent vertex) ;간선에 의해 직접 연결된 정점. 정점의 차수(degree) ;정점에 연결된 간선의 수. 경로(path) ;간선을 따라 갈 수 있는 길. 정점의 나열로 표시. 경로의 길이 ;경로를 구성하는데 사용된 간선의 수. 단순 경로(simple path) ;경로 중에서 반복되는 간선이 없는 경로. 사이클(cycle) ;단순 경로의 시작 정점과 종료 정점이 같은 경로. 연결 그래프(connected graph) ;그래프의 모든 정점들 사이에 경로가 존재하는 것. 트리(Tree) ;그래프의 특수한 형태. 사이클을 가지지 않는 연결 그래프. 완전 그래프(com.. 2019. 9. 4. 우선순위 큐(STL 힙 정렬) #include #include // STL 우선순위 큐를 이용한 내림차순 정렬. 최대 힙void heapSortDec(int arr[], int n){ priority_queue maxHeap; for (int i = 0; i 2019. 9. 3. 우선순위 큐(힙) 부모 노드의 키 값이 자식 노드의 키 값보다 큰 이진 트리. 최대 힙(max heap) ; 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) ; 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진트리 key(부모 노드) getParent(i).getKey()) // 루트가 아니고 부모노드보다 키값이 크면 { node[i] = getParent(i); // 부모를 자신노드로 끌어내림 i /= 2; // 한 레벨 위로 상승 } node[i].setKey(key); // 최종 위치에 데이터 복사 } // 힙의 루트 노드를 반환하고 힙을 재구성 HeapNode remove() { if (isEmpty()) .. 2019. 9. 3. 이전 1 2 다음
