본문 바로가기

전체 글80

BFS #include using namespace std; typedef long long ll; typedef pair pii; int R, C; int board[100][100]; int dir8[2][8]{ {0, -1, 0, 1, -1, -1, 1, 1}, {1, 0, -1, 0, 1, -1, -1, 1} }; bool dup[100][100]; void bfs(pii init) { int cr, cc, nr, nc; queue que; dup[init.first][init.second] = true; for (que.push(init); !que.empty(); que.pop()) { tie(cr, cc) = que.front(); for (int i = 0; i < 4; ++i) { nr = cr.. 2020. 12. 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.