알고리즘/종만북19 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. 트리 struct treeNode { int element; treeNode * parent; vector children; } * 이진 트리: 자식을 최대 두 개 갖는 트리 * 이진 탐색 트리: 이진트리. 어떤 노드에서 left엔 자기보다 작은 값, right엔 자기보다 큰 값을 유지하는 식 * 힙: 포화 이진트리. 노드가 들어갈 수 있는 자리가 비어있는 경우가 없으므로 일반적으로 배열로 구현. * 구간트리: * 상호 배타적 집합 구조(disjoint set) : 각 노드는 부모를 가리키는 포인터는 있지만 자식에 대한 정보는 없다. 2020. 2. 8. 이전 1 2 3 4 5 다음