jjj

세그먼트 트리 struct RMQ { int n; vector rangeMin; RMQ(const vector &arr) { n = arr.size(); rangeMin.resize(n * 4); init(arr, 0, n - 1, 1); } int init(const vector &arr, int left, int right, int node) { if (left == right) { return rangeMin[node] = arr[left]; } int mid = (left + right) / 2; int leftMin = init(arr, left, mid, node * 2); int rightMin = init(arr, mid + 1, right, node * 2 + 1); return rang..

위상정렬은 어떠한 일들에 대해 서로간의 우선순위가 주어졌을 때 모든 일에 대한 순서를 정렬하는 것이다. 1. 우선순위를 사이클이 없는 방향 그래프( 사이클이 있으면 모순이 된다 )로 나타낸 후 dfs가 종료된 순서의 역순이 위상정렬이 된다. 2. 자신에게 연결된 간선이 0개인 정점을 순서대로 큐에 넣어서 위상정렬을 할 수 있다. 0개인 정점을 처리한 후 자신이 연결하고 있는 정점에 연결된 간선의 개수를 감소시켜 또 다시 0인 정점들을 큐에 넣어 위상정렬을 한다. 백준 1766번: 문제집 여기서 우선순위큐를 사용한 이유는 문제에서 가능하면 번호가 작은 문제부터 풀어야 한다는 조건때문이다.#include #include #include using namespace std; vector adj; vector ..

LCA LCA 첫번째 방법 ( 구간 트리 + 전위순회 ) 백준 11437, 11438 각 정점을 전위순회할 때 거치는 모든 노드의 번호의 순서(자신으로 돌아올 때도 자기 자신을 넣는다 )를 trip 배열에 저장하고 그 trip 배열을 최소 구간 트리로 구현한다. 두 정점이 처음으로 등장하는 두 구간에서 순서가 가장 빠른 정점이 최소 공통 조상이 된다. ( 전위순회는 항상 부모가 자식보다 먼저 나오기 때문에 더 빠른 번호가 부모이다. ) 번호, 순서를 매핑하는 배열과 노드가 처음으로 등장하는 trip의 index를 저장한 배열이 필요하다. 아 그리고 입력이 어떤 정점이 부모인지를 모르기 때문에 두개 다 연결시켜놓고 dfs를 돌리면서 트리 형태를 만들어 주었다. 다른 알고리즘이 있던데 그 걸 확인해 봐야겠다..