본문 바로가기

Algorithm

 (49)
MEASURETIME (FENWICK TREE) #include #include using namespace std; struct FenwickTree { vector tree; FenwickTree(int n) : tree(n + 1) {} int sum(int pos) { ++pos; int ret = 0; while (pos > 0) { ret += tree[pos]; pos &= (pos - 1); } return ret; } void add(int pos, int val) { ++pos; while (pos > cn;..
MORDOR #include #include #include using namespace std; const int int_max = numeric_limits::max(); typedef struct DifficultyNode { int min, max; DifficultyNode() { min = int_max; max = 0; } DifficultyNode(int _min, int _max) : min(_min), max(_max) {} } DifficultyNode; typedef struct DifficultyQuery { vector querySource; int n; DifficultyQuery(vector &array){ n = array.size(); querySource.resize(n * 4); ..
RUNNINGMEDIAN #include #include #include using namespace std; typedef int KeyType; // 이 함수들은 문제 풀 때 쓰이진 않지만 (C++ STL 의 priority_queue를 대신 사용) // 기왕 구현했으니 넣어둠 void push_heap(vector &heap, KeyType key); void pop_heap(vector &heap); void swap(int *a, int *b); typedef struct Rng { int seed, a, b; Rng(int _a, int _b) : a(_a), b(_b) { seed = 1983; } int next() { int prevSeed = seed; seed = (seed * (long long)a + b)..
TREAP_INSERTION #include #include using namespace std; typedef int KeyType; typedef struct Node { KeyType key; int priority, size; Node *left, *right; Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(nullptr), right(nullptr) {} void setLeft(Node* newLeft) { left = newLeft; calcSize(); } void setRight(Node* newRight) { right = newRight; calcSize(); } void calcSize() { size = 1; if (left) si..
FORTRESS #include #include #include using namespace std; typedef struct Node { int x, y, r; int idx; vector childs; Node(int _x, int _y, int _r, int _idx) : x(_x), y(_y), r(_r), idx(_idx) {} } Node; void getLongestLeafPath(Node* const root); int height(Node* const root); bool compareNode(Node* a, Node* b); void PrintPrefix(Node* const root); void Insert(Node* const root, Node* const node); bool IsInside(..
TRAVERSAL #include #include using namespace std; typedef struct node { node* left; node* right; int key; node() { left = nullptr; right = nullptr; key = 0; } } node; vector TraversalPostfix(const node* root); node* GetTree(const vector &prefix, const vector &infix); int main() { int caseNum = 0; cin >> caseNum; int nodeCnt = 0; vector prefix, infix; for (int cIter = 0; cIter < caseNum; cIter++) { prefix.c..
HABIT #include #include #include #include using namespace std; int getMostHabit(string &habit, int minLength); int getCommonPrefixLength(string &s, int startIdx, int endIdx); vector getSuffixArray(string &habit); int main() { int caseNum = 0; cin >> caseNum; int k = 0; string habit = ""; for (int i = 0; i > k; cin.ignore(); std::getline(std::cin, habit); // Process int most = ge..
JAEHASAFE (KMP 알고리즘) #include #include #include using namespace std; int getMaxDup(const string &first, const string &second); vector getPartialMatch(const string &target); int main() { int caseNum = 0; int n = 0, result = 0; string first = "", second = ""; cin >> caseNum; for (int cIter = 0; cIter > n; cin.ignore(); std::getline(std::cin, first); result = 0; for (int spin = 0; spin < n; s..

티스토리툴바