본문 바로가기

알고리즘225

오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12.
DICTIONARY - 고대어 사전 (위상정렬) https://algospot.com/judge/problem/read/DICTIONARY 위상정렬 기본예제. dfs로 위상정렬 순서 정해주는 것 기록용 알파벳의 순서를 그래프로 표현하여 사이클이 있다면 INVALID 출력, 없다면 위상정렬된 순서로 출력 생략. dfs부분 유념 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace std; typedef lon.. 2020. 2. 12.
펜윅 트리 구간 합을 세그트리보다 좀 더 간결하고 메모리를 아끼면서 구하는 구조. 다음 코드는 1base. struct fwt { vector a; fwt(int n):a(n+1){} int sum(int p) { int ret = 0; while (p > 0) { ret += a[p]; p -= (p & -p); //최종 비트 지우기 } return ret; } void add(int p, int x) { while (p < a.size()) { a[p] += x; p += (p & -p); //최종 비트 더하기 } } }; int main() { FAST; fwt ft(10); for (int i = 1; i 2020. 2. 10.
이진 탐색 트리, 트립 보통 c++의 set이나 map을 이진탐색트리로 구현한다. (avl트리나 레드블랙 트리) 하지만 set이나 map은 k번째로 큰 원소가 무엇인지 알 수없다. 이런 기능을 가능하게 하는 구조로 '트립'이 있다. stl에서 사용하는 구조보단 느리지만 확률적으로 최악의 경우 로그시간에 동작한다. 노드에 값 외에 우선순위를 추가로 갖는다. 우선순위는 생성시 랜덤하게 부여된다. 트립은 다음 두가지 속성 (bs tree + heap)을 만족해서 treap이라고 부른다. 1. 모든 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 크다. 2. 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같다. typedef long lo.. 2020. 2. 10.

티스토리툴바