본문 바로가기

algorithm

 (4)
이중 연결 요소(BCC), 단절점, 단절선 SCC와 다르게 무향그래프에서 사용되는 개념 ㅁ BCC 어떤 BCC안에 속한 정점 하나와 그 정점에 인접한 간선들을 지웠을 때, 그 BCC 내에 남은 정점들은 모두 연결됨. (SCC와 유사, 하지만 간선끼리 묶어서 분류) 한번의 dfs로 BCC를 분류할 수 있다. int n, m, vst[MAX], counter; vector g[MAX]; vector bcc; //P는 간선 표현 stack s; int makeBCC(int u, int p) { int ret = vst[u] = counter++; for (int v : g[u]) if (v != p) { //아직 방문하지 않은 간선인 경우 스택에 u-v간선 넣음 if (vst[u] > vst[v]) s.push({ u,v }); //트리간선 if (v..
Euler Tour Tree(ETT) https://codeforces.com/blog/entry/18369 On Euler tour trees - Codeforces codeforces.com 이번에는 undirectd tree를 다루는 문제들에서 알아두면 좋은 Euler Tour Tree에 대해서 알아보도록 하겠습니다. Euler Tour의 사전적 정의는 다음과같이 "각 간선을 한번만 지나면서(양방향간선이라는 것을 유의하자) 그래프에 있는 모든 노드를 순회(traversal) " 하는 Tour를말하며 트리의 경우 DFS를 통해서 반드시 이런 Tour를 나타내는 배열을 얻을 수 있습니다. 입체적인 구조인 트리를 Euler Tour를 하게 되는 DFS를 통해 ETT[]={1,2,6,6,2,4,1,3,3,5,5}와 같이 순회한 노드로 이루어진..
knapsack https://www.acmicpc.net/problem/15759 세시간 시간재고 이 문제를 풀 수 있다면 이 포스팅은 건너 뛰어도 좋다. 흔히 가방문제라고 알려진 기본 dp 유형이다. 쉬운 유형이라고 생각했으나, 여러 방법으로 응용되는 문제들을 풀어보고 알게된 것들을 공유하고자 한다. https://www.acmicpc.net/problem/12865 냅색이 뭐였는지 기억이 안난다면 위 문제를 빠르게 다시 풀어보자. 이번 포스팅으로 위 문제처럼 한 가지 물품을 단 한번 만 넣어야 하는 경우, 한 가지 물품을 여러 개 넣을 수 있는 경우, 한 가지 물품을 최대 k개 넣을 수 있는 경우, 만족도가 이상하게 정의되는 경우 등에 대해 원리를 알고 문제를 풀어보려고 한다. 1차원으로 짤 수 있다고 해도, 2차..
Tree DP 그래프dp에 익숙하지 않은 사람들을 위해 자세히 쓰려고 한다. 이미 이 유형에 어느정도 익숙해졌다면 문제 위주로 따라와주면 될 것 같다. 마지막 문제에선 트리의 구조(루트)를 바꾸면서 백트래킹하여 정답을 갱신해나가는 rerooting에 대해서도 알아보겠다. 학습 시간은 최대로 잡아서 1번 문제 한시간, 2번 문제 한시간반, 3번 문제 두시간반 정도 보면 될 것 같다. 참조투명성에 대한 개념이 기억이 안난다면.. (대충 수학에서 다루는 함수생각하면 됨) https://ko.wikipedia.org/wiki/%EC%B0%B8%EC%A1%B0_%ED%88%AC%EB%AA%85%EC%84%B1 그래프에선 어떤 정점 u에 대한 상태가 인접한 정점 v에 대한 상태로 정의되며 참조 투명하다면 dp를 적용할 수 있다...

티스토리툴바