SCCC - Soongsil Computing Contest Club/2020 Winter-Study
-
19(마지막). 위상정렬, SCC, 2-SATSCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 25. 21:00
복습 위상정렬 1005번을 한번 보자. 그림의 노드들을 정렬한다고 치면 1, 2, 3, 4 혹은 1, 3, 2, 4순으로 정렬할 수 있다. 건물을 지을 때 1번은 2, 3번보다 앞에 있어야 하고 1, 2, 3번은 4번 앞에 있어야 한다. DAG, Directed Assigned Graph일때만 위상정렬이 가능하다. 사이클이 존재하지 않는 유향 그래프라는 뜻이다. DFS 종료의 역순은 위상정렬 순이다. DFS를 활용한 위상정렬: #include #include #include #include using namespace std; int T, N, K, W; vector g[100001]; int t[1001]; int fin[1001]; bool visited[100001]; vector st; void ..
-
18. 세그먼트 트리SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 25. 20:49
복습 세그먼트 트리 세그먼트 : 구간이라는 뜻. 2042번을 보면 방법 1 : for문 -> 업뎃은 빠르지만 쿼리가 느림 방법 2 : 누적합 -> 쿼리는 빠르지만 업뎃은 느림 정답 : 세그먼트 -> 쿼리도 빠르고 업뎃도 빠름 #include using namespace std; typedef long long int ll; const int MN = 1000000; int N, M, K; ll seg[MN*4+1]; ll Update(int idx, ll val, int n, int l, int r) { if(r K; for(int i=1; i> a; Update(i, a, 1, 1, N); } for(int i=0; i> c; if(c==1){ int x; ll y; cin >> x >> y; Upda..
-
17. 최대 유량SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 25. 20:46
복습 네트워크 플로우(최대 유량, Max Flow) 물의 발생지를 소스. 변수명은 s 추천 모든 물이 빨려 들어가는 마지막 점을 싱크. 변수명은 t 추천 각각의 파이프에 현재유량/최대유량을 저장하는 배열이 있어야 한다. 포드-풀커슨 알고리즘을 사용한다. 이 알고리즘의 핵심은 바로 유량의 대칭성을 만들어준다는 것이다. 어떤 경로로 유량을 흘렸으면 이 간선에 반대되는 간선을 만들고, 흘리는 유량 * -1 만큼 한 값을 넣어준다. dfs로 했을 때 시간복잡도는 O(EF). 단, E는 간선, F는 최대 유량 bfs로 했을 때 시간복잡도는 O(min(EF, V(E^2))). BFS로 구현한다. #include #include #include using namespace std; int N; int c[200][2..
-
16. LCA, sparse table, 오프라인 쿼리SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 25. 20:38
복습 LCA 두 정점의 깊이를 비교해서 더 깊은 정점을 끌어올린다. 두 정점의 깊이가 같다면 두 정점을 같이 끌어올린다. #include #include #include using namespace std; int main(){ int T; cin >> T; while(T--){ int N; cin >> N; int P[10001] = {}; for(int i=0; i> A >> B; P[B]=A; } int n1, n2; cin >> n1 >> n2; set s; while(1){ s.insert(n1); if(P[n1]==0) break; n1=P[n1]; } while(1){ if(s.find(n2) != s.end()){ cout > a >> b; cout
-
15. 트리 순회, 트리의 지름SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 25. 19:55
복습 트리 순회 1991번을 보자. 전위 순회는 dfs한 순서대로 그대로 출력한다. (부모)(왼쪽자식)(오른쪽자식) 중위순회는 (왼쪽자식)(부모)(오른쪽자식) 이런식으로 출력된다. 후위순회는 (왼쪽자식)(오른쪽자식)(부모) 이런식으로 출력된다. #include using namespace std; char L[200], R[200]; void Pre(char n){ cout a >> b >> c; L[a] = b; R[a] = c; } Pre('A'); cout W; for(int i=0; i> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); cout > v >> w; G[u].push_back({v, w}); G[v].push_back({u, w..
-
14. 누적 합SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 17:52
복습 누적합 or 부분합 or Prefix Sum or Partial Sum 11659문제를 보면, 입력이 주어질 때 마다 합을 구해서 출력하면, O(MN)으로 시간초과가 뜨게 된다. 이 문제는 미리 합을 구해 놓고 질문이 들어올 때마다 값을 출력해야 한다. S[i] : 1~i까지의 합이라고 정의하고, S[i] = S[i-1] + A[i]의 식을 사용한다. L~R까지의 합은 S[R] - S[L-1]으로 구할 수 있으며, 이는 O(1)의 시간복잡도를 가지게 된다. #include using namespace std; int dp[100001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; for(int ..
-
13. 분할 정복SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 15:19
복습 분할 정복 Divide and Conquer(DNC) merge sort를 할 때 생각해보면, 한 그룹을 둘로 나누는 과정을 반복해 모두 쪼갠다음, 다시 합쳐나가는 방식이다. 이런 문제 풀이 방식을 분할정복이라고 한다. 하나의 거대한 문제를 작은 여러개의 문제로 나누는 것. 1725번을 보자. 만약 가운데 두개를 고정하는 문제였다면, 그 두개를 기준으로 양 옆에 높이가 더 높은 막대를 포함시키면서 탐색한다. 이를 그리디 방법이라고 부르겠다. 이를 이용해서 dnc(L, R)을 정의하겠다. dnc(L, R) = L ~ R 구간에서의 직사각형 최대 넓이 dns(L, R) = max( dns(L, mid), dns(mid+1, R), 그리디방법 ) 즉, 가운데를 잘랐을 때 우리가 구할 답은 가운데 기준 왼..
-
12. 파라메트릭 서치SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 15:18
복습 파라메트릭 서치(이분탐색) 2805번을 보면, f(h) : 높이를 h로 설정해서 자르면 얻는 나무의 양 이걸 높게 설정할수록 적게 얻고, 많이 설정할수록 많이 얻으니깐 항상 감소하는 모양이 나온다. 이걸 이진탐색으로 적절한 구간을 찾는다. 최대값의 최소, 최소값의 최대꼴이면 대부분 파라메트릭 서치를 활용할 수 있다. #include using namespace std; typedef long long int ll; const int MN = 1000001; int T[MN]; int N, M; ll f(ll h){ ll sum=0; for(int i=0; i h) sum+=T[i]-h; } return sum; } int main(){ cin >> N >> M; for(int i=0; i> T[i]..
-
11. 유니온 파인드SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 15:16
복습 Union-Find Tree (Disjoint Set) Union과 Find 연산이 있는 tree를 저렇게 부른다. (1) (2) (3) (4) (5) 이렇게 다섯 그룹이 있을 때 1, 2를 union 하면 => (1, 2) (3) (4) (5) 또 3, 4를 union 하면 => (1, 2) (3, 4) (5) 여기서 find(3)을 하면 3이 속한 그룹의 대표자를 찾을 수 있다. find(4)를 하면 find(3)과 같은 값이 나온다. 이 자료구조의 단점은 c++에 구현이 안되어있다는 것과 find, union 연산의 시간복잡도는 평균 아커만함수의 역함수를 가진다. O(1)이라고 보면 된다. 첫번째 구현방법 : #include using namespace std; const int MN = 10..
-
10. 최단경로, 플로이드-와샬, 다익스트라SCCC - Soongsil Computing Contest Club/2020 Winter-Study 2020. 2. 10. 15:14
복습 최단경로 그래프에서 최단경로를 찾고 싶으면 어떡할까? 다익스트라, 벨만-포드, 플로이드-와샬 등등을 사용할 수 있다. 그 중 이번시간엔 다익스트라와 플로이드를 해본다. 플로이드-와샬 (Floyd-Warshall) 줄여서 그냥 플로이드라고 하자. 일단 최단경로 알고리즘의 일종인 플로이드는 최단경로 알고리즘 중 가장 짧고 간단한 알고리즘이다. #include using namespace std; int dp[100][100]; const int INF = 1e9; int main(){ int N, M; cin >> N >> M; for(int i=0; i> v >> w; u--, v--; dp[u][v] = min(dp[u][v], w); } for(int k=0; k> w; u--, v--; G[u]..