본문 바로가기

전체 글93

2020 인하대학교 프로그래밍 경진대회(IUPC) 참여 팀 인덕이 팬클럽으로 참여하여 총 아홉 문제를 풀었다. 대회 직전 예상치 못한 애로사항이 많았지만 아무튼 결과가 좋아서 하루 종일 기분이 좋았다. 내가 푼 문제는 A - 연길이의 이상형 / B - Sort 마스터 배지훈의 후계자 / H - 앨범정리 / K - 인덕이의 고민 이다. A번 연길이의 이상형 20540번: 연길이의 이상형 졸업을 앞둔 연길이는 크리스마스가 다가올수록 외로움을 느낀다. 그런 연길이를 위해 동우는 소개팅을 시켜주지는 않고 연길이의 이상향을 찾는 것을 도와주고자 한다. MBTI 신봉자인 연길이는 www.acmicpc.net A번이 매우 쉬워 보이니 빨리 풀라고 해서 빨리 풀었다. B번 Sort 마스터 배지훈의 후계자 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스.. 2021. 1. 10.
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.

티스토리툴바