본문 바로가기

2-1 학기/Data Structure9

[자료구조] 해싱(Hashing) 해싱(Hashing) 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다. 검색방법 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동한다. 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 실패 해싱 용어 정리 충돌: 서로 다른 키 값에 대해 해싱 함수로 구한 버킷 주소가 같은 경우 동거자: 서로 다른 키 값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키 값들 오버플로우: 버킷에 비어 있는 슬롯이 없는 포화 버킷 상태에서, 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태 키 값 밀도: 사용 가능한 전체 키 값들 중 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도 적재 밀도: 해시 .. 2023. 6. 16.
[자료구조] 정렬(Sort) 동기리스트: 하나 이상의 필드로 된 레코드의 집합키: 레코드를 구분하기 위해 사용되는 필드순차탐색: 레코드를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사하는 것template int SeqSearch(E *a, const int n, const K& k){ // a[1:n]을 왼쪽에서 오른쪽으로 탐색한다. // a[i]의 키 값이 k와 같은 가장 작은 i를 반환한다. // 그런 i가 없으면, 0을 반환한다.int i;for (i = 1; i n) return 0;return i;}n개의 레코드를 탐색하기 위해 O(n)의 시간이 걸린다. 이원탐색(Binary Search): 정렬된 n개의 레코드를 탐색하기 위해 O(log n)의 시간이 걸린다.보간법(interpolation): 리스트가 정렬돼.. 2023. 6. 6.
[자료구조] 최단 경로 최단경로: 하나의 정점에서 다른 모든 정점까지(Single-source Shortest Path Problem) 시작점 v에서 G의 나머지 모든 정점까지의 최단 경로 시작점 v와 목표점 t까지의 경로 중, 경로를 구성하는 간선들의 가중치 합이 최소가 되는 경로 방향 그래프 G = (V, E), weight[l, j] >=0 Dijkstra 최단 경로 알고리즘 Dijkstra 최단 경로 알고리즘의 원리 S: 최단 경로가 발견된 정점들의 집합 weight[i, j]: 간선 의 가중치 Dist[i]: S에 속하지 않은 i에 대해서, v에서 시작하여 S에 있는 정점만을 거쳐 정점 i에 이르는 최단 경로의 길이 처음 S에는 시작점 v만 포함, Dist[v] = 0 가장 최근에 S에 첨가된 노드를 u라고 하자. u.. 2023. 6. 2.
[자료구조] 최소 비용 신장 트리(Minimum-cost Spanning Tree) 신장 트리(Spanning Tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리이다. 최소 비용 신장 트리(Minimum-cost Spanning Tree) 최소 비용 신장 트리란 최저의 비용을 갖는 신장 트리이다. 연결 무방향 그래프에서 최소 비용 신장 트리를 구하기 위해서는 세 가지 상이한 알고리즘을 사용할 수 있다. 모두 갈망법(greedy method)이라고 하는 설계 전략을 사용하고 있다. Kruskal 알고리즘 Prim 알고리즘 Solin 알고리즘 그래프 내에 있는 간선들만을 사용해야 한다. 정확하게 n-1개의 간선만을 사용해야 한다. 사이클을 생성하는 간선을 사용해서는 안 된다. 탐욕 알고리즘(Greedy Algorithm) 매 순간 최적의 해를 단계별로 도출한다. 각 단계에서.. 2023. 5. 29.
[자료구조] 그래프 순회(Graph Traversal) 그래프 순회(Graph Traversal) 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 깊이 우선 탐색(DFS: depth first search) 1. 시작 정점 v를 결정하여 방문한다. 2. 정점 v에 인접한 정점 중에서 (a) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 v로 하여 다시 2번을 반복한다. (b) 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2번을 반복한다. 3. 스택이 공백이 될 떄까지 2번을 반복한다. ❗️시간 복잡도❗️ 인접 리스트의 노드들의 탐색을 끝내는 시간 O(e) O(|V| + |E|) = O(|V|) + O.. 2023. 5. 29.
[자료구조] 그래프(Graph) 그래프(Graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 관계를 가지는 원소들을 표현하기 위한 자료구조 그래프 G는 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다. V는 그래프에 있는 정점들의 집합 E는 정점을 연결하는 간선들의 집합 무방향 그래프(Undirected Graph) 두 정점을 연결하는 간선의 방향이 없는 그래프이다. 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현한다. 이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미한다. 위의 그래프를 집합으로 표현하면 다음과 같다. V(G1) = {A, B, C, D} E(G1) = {(A,B), (A,D), (B,C), (B,D), (C,D)} V(G2) = {A, B, C} V(G.. 2023. 5. 29.
[자료구조] 이원 탐색 트리(Binary Search Tree) 사전(Dictionary) 사전(Dictionary)은 쌍의 집합으로서 각 쌍은 키와 이에 연관된 원소로 구성된다. 같은 key를 갖는 두 쌍은 없다고 가정한다. template class Dictionary{ public: virtual bool IsEmpty() const = 0; virtual pair *Get(const k&) const = 0; virtual void Insert(const pair&) = 0; virtual void Delete(const K&) = 0; }; 키와 원소의 데이터 값은 각각 K와 E이다. 이진 탐색 트리(Binary Search Tree) 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리.. 2023. 5. 29.
[자료구조] 힙(Heap) 우선 순위 큐(Priority Queue) 우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다. template class MaxPQ{ public: virtual ~MaxPQ(){ }// 가상 파괴자 virtual bool IsEmpty() const = 0;// 우선순위 큐가 공백이면 true 반환 virtual const T& Top() const = 0;// 최대 원소에 대한 참조를 반환 virtual void Push(const T&) = 0;//우선순위 큐에 원소를 삽입 virtual void Pop() = 0;// 최대 우선순위를 가진 원소 삭제 }; 시간 복잡도 IsEmpty(): O(1).. 2023. 5. 29.
[자료구조] 트리(Tree) 트리(Tree) 트리(Tree)는 원소들 간에 1 : N 관계를 가지는 비선형 자료구조이다. 한 개 이상의 노드(node)로 이루어진 유한 집합으로서 노드 중에는 루트(root)라고 하는 노드가 하나 있고 나머지 노드들은 n(>=0)개의 분리집합 T1, ,,, Tn으로 분할될 수 있다. 여기서 T1, ,,, Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다. 한 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 예를 들어 트리의 구조가 다음과 같을 때, A의 차수는 3이고, C의 차수는 1, L의 차수는 0이다. 차수가 0인 노드를 리프(leaf) 또는 단말 노드(terminal node)라 한다. 그 외의 나머지 노드들은 비단말 노드(nonterminal node)라 .. 2023. 5. 29.

티스토리툴바