반응형 2019/1031 [알고리즘 공부] 디닉 알고리즘(Dinic's Algorithm) Max flow를 구하는 데 있어, PS에서 쓸 수 있는 알고리즘 중 가장 빠르다고 한다. O(V^2 * E)의 시간복잡도를 가진다. 설명은 아래에. 1. BFS로 유랑이 남은 간선을 기준으로 src에서 dst 노드까지 최단 거리를 구한다.(이를 level graph라고 함) --> BFS라서 O(E)에 가능하다. 선형 시간! 2. DFS로 level graph에서 blocking flow를 흘려주면서 더 이상 못 보낼 때까지 반복한다. --> 생각하기 좀 어려웠는데 한 번 flow를 흘려줄 때마다 bottleneck은 막혀버리니까 최소한 edge하나는 막혀버림. 그리고 edge가 막힐 때 dead end(가다가 막혀버리는 vertex)를 최대 V번 만날 수 있으므로, 많아야 VE번 증가경로.. 2019. 10. 15. [c++] 백준 #3830 교수님은 기다리지 않는다. 맨처음엔 정말 naive하게 O(N^2) dfs 풀이로 진행했다가 TLE를 맛보고 union disjoint set을 이용해서 풀어야 한다는 것을 알게 되었다. b가 a보다 무겁다는 걸 그래프로 나타내면 아래와 같다. b가 무거우니까 diff[b] - k = diff[a]가 된다. 여기서 b와 a에게 부모가 있다는 걸 생각하고 그래프를 그려보자. b의 부모에 a의 부모를 붙일거면 diff[b] - k = x + diff[a]가 성립한다. 따라서 x = diff[b] - diff[a] - k가 된다. 반대로 a의 부모에 b의 부모를 붙일 거면 -x를 붙여주면 된다. ** 각 테케마다 p, diff, n을 초기화해줘야하는데 여기서 실수로 for문 2개를 넣어버려서 이상한 곳에서 TLE가 나서 나.. 2019. 10. 14. [c++] 백준 #6531 이런 문제는 유치원생도 해결할 수 있어 분할정복 문제이다. 이때 중복해서 계산하는 게 있어서 시간초과를 피하기 위해서는 dp배열을 써주자. 코드나 로직 자체는 최적화가 덜된 것 같지만.. 로직을 간단하게 설명하면, {}으로 되어 있으면 set이고, {}안에 있는 것들이 ","를 기준으로 elem인지 확인을 해주면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back #define N_MAX 100010 string str; int isElem(int a, int b); int isSet(int a, int b); vector dp.. 2019. 10. 13. [c++] 백준 #1194 달이 차오른다, 가자. 너무 복잡하게 생각했는데, 그냥 BFS를 하는데 key를 가지고 있는 조건들을 비트마스킹하면 된다. key를 획득한 정보나 움직인 횟수를 count하는 변수를 잘 관리해야 꼬이지 않는다..ㅠㅠ for문 체크할 때마다 초기화해줘야 하는데 잘못하면 중복해서 count되는 경우도 있고 그렇다. 공간 복잡도는 A~F의 key만 가지고 있는 지 확인하면 되고, 전체 map이 50x50이니까 총 O(50*50*2^6)의 복잡도를 가진다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back vector mir.. 2019. 10. 13. 이전 1 2 3 4 ··· 8 다음 반응형