알고리즘225 이분그래프 (bipartite graph) 어떤 그래프의 모든 노드를 두가지 색 중 하나로 칠하되, 이웃 노드의 색이 모두 다르게 만들 수 있다면 그 그래프는 이분그래프이다. 홀수개의 간선으로 이뤄진 사이클이 없으면 이분그래프이다! void dfs(int u, int p) { vst[u] = vst[p]==1?2:1; for (int v : adj[u]) { if (v == p) continue; if (vst[v] && !fin[v] && vst[v]==vst[u]) isNotBipartite = true; else if (!vst[v]) dfs(v, u); } fin[u] = true; } 2020. 1. 22. BOJ 1176 - 섞기 (bit, dp) https://www.acmicpc.net/problem/1176 dp using bitfield중 기본문제. 최대 16명의 학생들의 키와 k값이 주어진다. 학생들을 일렬로 배치했을 때 모든 학생들의 인접한 학생과의 키 차이가 k이초과인 경우의 수를 구해라. f(s,t) : 현재 s, 마지막으로 배치된 인원이 t인 경우의 수 ans = f(0,n) -- (t==n인 경우 아무 인원이나 배치할 수 있다. [0base]) s==(1> a[i]; memset(dp, -1, sizeof(dp)); cout 2020. 1. 22. 비트셋 dp 문제모음 https://solved.ac/problems/algorithms/87 2020. 1. 22. CSES PS - Elevator Rides (bit, dp) https://cses.fi/problemset/task/1653/ 쉬운 설명의 어려운 문제 bit쓰는 dp중엔 기본문제인 듯 하다. https://suuntree.tistory.com/124?category=797985 비슷한 유형의 더 어려운 문제 최대 20명의 사람들의 몸무게가 주어질 때, 최대 하중이 x인 엘레베이터에 사람을 채워 보내는 최소 운행 횟수를 구해라. (몸무게 2020. 1. 22. 이전 1 ··· 23 24 25 26 27 28 29 ··· 57 다음