벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm) 특정 노드에서부터 모든 노드로 가는 최단 경로를 구하는 알고리즘. 그래프에 “음수 사이클"이 있는 경우 찾아낼 수 있음. 시간복잡도는 O(nm) 음수 사이클 음수 사이클이 있는지 판단하기 위해서는 n번의 라운드를 추가로 진행해 주면된다. 만약, n번째 라운드에서도 감소하는 경우가 있다면, 음수 사이클이 있다고 판단할 수 있다. 코드 1 2 3 4 5 6 for (i = 0; i <= V; i++) d.push_back(INF); d[x] = 0; for(int i = 1; i <= n - 1; i++) for(auto t : edge(a,b,c)) // a 에서 b로 가는 간선, 가중치 c d[b] = min(d[b], d[a] + c);
https://www.acmicpc.net/problem/1780
풀이: [백준]2630 색종이 만들기 참고
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream>using namespace std; int n, c[2200][2200], W = 0, B = 0, D = 0; void se(int x, int y, int a) { bool w = true, b = true, d = true; for (int i = 0; i < a; i++) for (int t = 0; t < a; t++) if (!
https://www.acmicpc.net/problem/2630
풀이: n을 2로 나누어 가며 1로 이루어진 곳인지 0으로 이루어진 곳인지 판단한다.
0으로 이루어져있다면 W를 +1 , 1로 이루어져있다면 B를 +1 해준다.
하얀색 색종이와 파란색 색종이의 갯수를 출력한다.
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <iostream>using namespace std; int n, c[129][129], W = 0, B = 0; void se(int x, int y, int a) { if (x >= n || y >= n || !
https://www.acmicpc.net/problem/6549
풀이: 값을 하나씩 받아온다.
현재 값보다 스택에 있는 값이 더 크다면,
max(현재 max값, 스택의 탑값 * (스택의 탑 바로 전 값의 위치와 현재 위치의 차이)) 을 수행하고, 현재 탑에 있는 값을 pop한다.
스택에 모든 값이 현재 있는 값보다 작거나 같다면, 스택에 현재 값을 push한다.
모든 값을 받았다면, 스택이 빌 때까지
max(현재 max값, 스택의 탑값 * (스택의 탑 바로 전 값의 위치와 전체 히스토그램의 길이의 차이))
를 수행한다.
히스토그램의 길이가 0일경우 반복을 중지한다.
다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘(Dijkstra Algorithm) 특정 노드에서부터 모든 노드로 가는 최단 경로를 구하는 알고리즘. 가중치가 음수인 간선이 없는 경우에만 사용할 수 있다. 시간복잡도 : O(n + mlog m) (n : 노드의 개수, m : 간선의 갯수) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 for (i = 0; i <= V; i++) d.push_back(INF); d[k] = 0; p.push({ 0, k }); while (!
