0850

최소 신장 트리(Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘이다. 최소 신장 트리란 그래프에서 모든 정점을 최소 비용으로 연결하는 트리이다. 프림 알고리즘 다음 과정을 따른다. 1. 시작 정점을 하나 정함.2. 연결 가능한 간선들 중 가장 비용이 낮은 간선을 선택3. 해당 간선이 연결하는 정점이 아직 MST에 포함되지 않았다면 추가4. 1~3을 모든 정점이 연결될 때까지 반복 프림은 O(ElogV)의 시간 복잡도를 가지며, priority_queue를 사용하여 구현할 수 있다.(MST 구현에 사용되는 다른 알고리즘인 크루스칼은 O(ElogE)이다. 따라서 간선이 많은 경우는 프림이 유리하다.) int mst() { priority_queue, vector>, greater>..

위상 정렬이란 어떤 일들을 순서대로 해야 할 때, 선행 조건이 있는 작업들의 실행 순서를 정하는 방법이다. 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 적용가능하다. DFS기반과 BFS기반으로 구현할 수 있다. 이 글에서는 BFS기반으로 작성했다. 위상 정렬 알고리즘의 작동 과정은 아래와 같다. 1. 진입 차수가 0인 node를 queue에 넣는다.2. queue에 넣은 노드의 다음 node의 진입차수를 1 줄인다.3. q가 비어있을 때까지 2를 반복한다. 코드로 작성하면 아래와 같다. int st[32001]; // 노드들의 진입차수vector graph[32001]; // 노드 연결int N; // 노드의 수queue q;vector ans;void ts() { for..

값: 1 2 2 2 3 4 5 6index: 0 1 2 3 4 5 6 7일때, 값 2를 찾으려고 한다. upper_bound에서는 index: 4 (값 2 초과가 처음 나오는 위치)lower_bound에서는 index: 1 (값 2가 처음 나오는 위치) upper_bound// upper_boundint ans;int s = 0;int e = arr.size() - 1;while(s lower_bound// lower_boundint ans;int s = 0;int e = arr.size() - 1;while(s

문자열 저장, 탐색을 효율적으로 하기 위한 트리 형태의 알고리즘 아래 코드는 문자열을 추가하는 코드와 k번쨰 단어를 출력하는 코드(응용)int k = 0; // 현재까지 찾은 단어 수int K; // 찾고자 하는 K번째 단어bool flag = false; // 출력 후 종료 플래그class Trie {private: Trie* child[27]; bool finish = false; // finish == true면 문자열 bool check = false;public: Trie() { for (int i = 0; i insert(w + 1); }void printWord(const string& prefix) { // k번째..

구간합#include #include using namespace std;int segTree[100000];int N, M;void update(int n, int s, int e, int ii, int val) { if (s > ii || ii > e) return; segTree[n] += val; if (s == e) return; int m = (s + e) / 2; update(n * 2, s, m, ii, val); update(n * 2 + 1, m + 1, e, ii, val);}int query(int n, int s, int e, int l, int r) { if (e r) return 0; if (s >= l && e 구간합 + 최대, 최소#include #include using..

한 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘 아래는 priority_queue를 사용한 dijkstra 구현void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) { priority_queue> pq; for(int i = 0; i 기본1: https://www.acmicpc.net/problem/1753기본2: https://www.acmicpc.net/problem/11779 응용1: https://www.acmicpc.net/problem/1162응용2: https://www.acmicpc.net/problem/1854