본문 바로가기

전체 글92

Good Bye, BOJ 2020! 특별상 을 받아서 기분이 좋다 ㅎㅎ 2020. 12. 31.
연속한 수의 XOR sum ll xorSum(ll n) { int m = n % 4; if (m == 0) return n; if (m == 1) return 1; if (m == 2) return n + 1; return 0; } 1부터 n까지의 수의 XOR sum은 위와 같다. 자세한 내용은 여기에서 볼 수 있다. ll xorSum(ll l, ll r) { return xorSum(l - 1) ^ xorSum(r); } 구간 [L : R] 의 xor 합 역시 같은 두 수를 xor 하면 0이 된다는 사실을 이용하여 구할 수 있다. 2020. 12. 25.
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.

티스토리툴바