본문 바로가기

Category

 (7)
이중 연결 요소(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..
선분에 대한 질의 https://codeforces.com/blog/entry/72330 위 에디토리얼과 그 댓글들을 참조했습니다. 이런 선분들이 있을 때, 교차하는 선분 쌍 (u,v), (v,w)를 만들 수 있는 방법에 대해 소개하고자 한다. 쉬울 것 같지만 필자 기준으로 이해하는 데 상당한 시간이 걸렸다. 1. 각 정점의 양 끝점을 P a[MAX]에 담아둔다. 2. vector evs에 (a[i].first, i) 와 (a[i].second, i)를 모두 담아서 오름차순 정렬한다. 3. set cand를 마련한다. (아직 교차할 정점을 찾을 여지가 남은 정점의 (우측끝점, 정점번호)를 기억해 두기 위함.) 4. 정렬해둔 evs를 차례로 순차하면서 ( evs는 선분이 아닌, 선분에 속한 끝점과 그 선분의 번호를 의미함에..
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를 적용할 수 있다...
bithack LIST 홀수 판별 -1 판별 부호 판별 두 수의 부호 일치 2의 승수 판별 2의 승수로 곱하기, 나누기 2의 승수로 나눈 나머지 2의 승수로 올림 완전이진트리 swap 가장 작은 비트가 나타내는 값 bit로 나타낸 이진 순열의 다음 순열 bool 배열 메모리 최적화 1. 홀수 판별 모든 홀수는 이진수로 나타내면 0번 비트가 켜져있으므로, 0번 비트를 검사해주면 된다. 1 2 if (a & 1) // a가 홀수 else if (!(a & 1)) // a가 짝수 cs 2. -1 판별 -1의 이진수표현은 모든 비트가 켜진 것이므로, ~(-1)은 모든 비트가 꺼진 0이다. 따라서 ~a가 0이라면 a는 -1, ~a가 0이 아닌 수라면 a는 -1이 아닌 수이다. 1 2 3 4 5 for(int i = n - 1;..
모양 정돈 짜잘하고 어디 쓸데도 없어보이지만 KOI, swexpertacademy에서 풀어 볼 문제가 있기 때문에 알아두면 좋을 것 같다. bfs, 정렬 등 방법은 많지만 가장 간단한 방법을 소개하려고 한다. 이 방법은 이해만 해두면 구현은 두세줄 정도로 매우 쉽다! 빨강, 초록, 파랑 바구니에 여러개의 빨강, 초록, 파랑공이 무작위로 담겨있을 때, 각 공을 색깔에 맞는 바구니에 넣고자 한다. 두 공의 위치를 바꾸는 행동을 최소 몇 번해야 완벽히 정돈될까? 다음과 같은 상황을 생각해보자. (1) 우선 빨간색 바구니부터 채운다. 빨간 바구니의 초록공은 최대한 초록 바구니의 빨간공과 교환한다. 빨간 바구니의 파란공은 최대한 파란 바구니의 빨간공과 교환한다. 더보기 (이 경우엔 빨간 바구니의 초록공이 파란 바구니로 들어..

티스토리툴바