본문 바로가기
반응형

전체 글82

[c++] 백준 #5000 빵정렬 정렬을 할 때마다 규칙성을 찾아야 하는 게 문제인데 나는 그걸 못 찾아서 친구의 풀이를 듣고 깨달음을 얻었다. 정렬을 할 때마다 역순 pair의 홀짝성이 유지가 된다는 것이 특징. 예를 들어 (4, 3, 2)는 (4, 3), (3, 2), (4, 2) 총 3개의 역순 pair를 가진다. 이를 빵정렬하면 (2, 4, 3)이 되는데 이거는 역순 pair를 (4, 3) 하나만 가진다. 그러면 역순 pair의 수가 홀수인 순열은 아무리 빵정렬을 해도 역순 pair의 수가 홀수개이다. 역순 pair 수가 짝수개가 죽어도 될 수 없다는 의미. 그러므로 주어진 두 input의 역순 pair 수를 세보고 둘다 짝수거나 둘다 홀수면 Possible, 아니면 Impossible을 띄우면 된다. 역순 pair를.. 2019. 11. 5.
[알고리즘 공부] 디닉 알고리즘(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.
반응형

티스토리툴바