학과공부/자료구조13 Digraphs 개요 모든 간선이 directed인 그래프 Directed DFS 간선은 탐색 시점을 기준으로 discovery, back, forward, cross의 네 종류로 분류한다. discovery: end vertex가 unexplored인 edge back: end vertex가 ancestor인 edge forward: end vertex가 descendant인 edge cross: end vertex가 ancestor도 descendant도 아닌 정점인 edge DAG와 위상 순서 DAG: Directed Acyclic Graph 위상 순서: 각 정점을 v1, v2, ..., vn이라고 할 때 모든 간선 (vi, vj)에 대해 i < j가 성립하는 순서 위상 정렬 알고리즘 시간복잡도 O(n + m)의 .. 2020. 12. 8. BFS와 DFS 그래프 용어 정리 Subgraph: 그래프 G의 서브그래프 S에 대해, S의 정점과 간선은 G의 정점과 간선의 subset이다. Spanning subgraph: G의 모든 정점을 포함하는 Subgraph Connected graph: 임의의 두 정점 사이에 반드시 path가 존재하는 그래프 Connected component: Maximal connected subgraph Tree: 사이클이 없는 connected graph Forest: 사이클이 없는 무향그래프, Forest의 connected components는 각각 트리이다. Spanning tree: 트리인 Spanning subgraph, 한 그래프에 대해 여러가지 모습으로 존재할 수 있다. 그래프의 Spanning forest는 fore.. 2020. 12. 8. Graphs 개요 그래프는 (V, E) 쌍으로 나타낸다. V는 Vertices로 정점의 set을, E는 Edges로 간선의 collection을 의미한다. 둘 모두 position ADT로, 임의의 원소를 저장할 수 있다. Edge의 종류 Directed edge: 순서가 있는 정점 (u, v) 쌍. 각각 origin, destination이라고 한다. Directed graph: 모든 간선이 directed인 그래프 Undirected edge: 순서가 없는 정점 (u, v) 쌍. Undirected graph: 모든 간선이 undirected인 그래프 용어 정리 endpoints: 어떤 간선에 대해 양 끝에 연결된 두 정점. adjacent vertices: 간선으로 직접 연결된 두 정점. incident: 어떤.. 2020. 12. 7. Hash Table 개요 비효율적이었던 맵을 개선 해보자. 맵의 모든 method를 그대로 가지고 있다. 추가로 볼만한 건 다음과 같다. entrySet(): 맵의 모든 entry를 리스트로 반환한다. keySet(): 맵의 모든 key를 리스트로 반환한다. / 파이썬의 dict.keys() values(): 맵의 모든 value를 리스트로 반환한다. / 파이썬의 dict.values() 해시 테이블은 해시 함수 h와 크기 N의 배열 (table)로 이루어진다. 해시 함수 해시 함수 h는 주어진 키 x를 정수 [0, N)에 매핑한다. (예: h(x) = x % N) h(x)는 x에 대한 hash value이고, {키: 값} 쌍을 테이블 index h(키)에 저장하게 된다. 일반적으로 Hash code와 Compression.. 2020. 12. 7. Map & Dictionary 개요 탐색이 용이한 {키: 값} entry의 collection. 맵은 중복 키를 허용하지 않고, 딕셔너리는 중복 키를 허용한다. 맵과 딕셔너리의 Entry ADT {키: 값} 쌍을 저장한다. 다음 네 가지 메소드를 지원한다. key(): 키 반환 value(): 값 반환 setKey(k): 키를 k로 변경 setValue(v): 값을 v로 변경 맵, 딕셔너리 ADT 두 ADT는 공통적으로 다음 메소드를 지원한다. find(k): 키가 k인 entry를 탐색해 포인터를 반환한다. 존재하지 않는 경우 iter::end를 반환한다. put(k, v): 키가 k, 값이 v인 entry를 삽입한다. erase(k): 키가 k인 entry를 삭제한다. 추가로 size, empty, begin, end를 지원할 수.. 2020. 12. 7. Binary Search Tree 개요 노드에 키(또는 {키, 값} 쌍)를 저장하는 이진트리로, 다음 성질을 만족한다. 노드 v와 왼쪽 자식 u, 오른쪽 자식 w에 대해 key(u) ≤ key(v) ≤ key(w) 를 만족한다. 리프 노드는 아무것도 저장하지 않고, 트리를 중위 순회하면 키 오름차순으로 방문하게 된다. 탐색 키 k를 찾으려면, 루트 노드에서 출발해 k와 현재 노드의 키를 비교하며 탐색한다. k가 현재 노드의 키보다 작다면 왼쪽 노드로, 크다면 오른쪽 노드를 탐색한다. 리프 노드에 도달하면 키 k가 존재하지 않음을 의미한다. 삽입 먼저, 탐색과 같은 방법으로 키 k가 이미 존재하는지 판단한다. 리프 노드에 도달하면 해당 위치에 k를 삽입한다. 삭제 먼저 k에 대해 탐색하여 노드 v를 찼았다고 가정하자. v의 두 자식이 모두.. 2020. 12. 4. 이전 1 2 3 다음
