본문 바로가기

분류 전체보기327

벨만포드, SPFA 시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다 *모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다. O(EV) 필요한 것: int dist[MAX]{0} vector adj[MAX]; //혹은 vector edge 일반적인 코드. 음의 사이클 검출방법 int main() { int N, M, dist[MAX], st, en; fill(dist, dist + N, INF); vector adj[MAX]; dist[st] = 0; bool minusCycle = false; for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재 //이하 두개의 for문 .. 2019. 8. 18.
다익스트라 시작점이 정해진 상태이고 가중치>=0일 때 최단경로 구할 때 사용. 사이클이 있어도 사용가능. 하나의 정점을 검사할 때마다 모든 간선에 대해 검사하고, 최소힙(우선순위 큐)에 들어가는 것은 최악의 경우 간선 개수만큼 들어가므로 O(ElogE) bst(set)을 사용해서 유효한 {dist, i}만을 유지한다면 O(ElogV)지만 속도가 크게 차이 안날 뿐더러, 우선순위 큐의 시간복잡도 상수가 더 작다. 구현이 편한 ElogE코드를 사용하자 필요한 것 : bool vst[MAX] {0} int d[MAX] {INF} vector g[MAX] priority queue (dist 가장 가까운 것부터) int main() { bool vst[MAX] = {0}; vector g[MAX]; //{도착지,가중치} .. 2019. 8. 18.
에라토스테네스, 소수 필요한것 : 불린형 배열 bool isPrime[MAX+1]; fill(isPrime, isPrime + MAX+1, true); isPrime[1] = false; for (int i = 2; i 2019. 8. 18.
Segment Tree, LIS https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 가장 기본문제. 구간의 합,최댓값,최소값 등, 원소간 결합,교환법칙이 성립하는 연산에대해 구간의 연산을 구할 수 있는 알고리즘. .. 2019. 8. 18.

티스토리툴바