플로이드 와샬 알고리즘은 다익스트라, 벨만 포드 알고리즘과 달리 '모든 정점에서 다른 정점까지의 최단거리'를 구한다. 다익스트라처럼 큐에 넣어서 거쳐가는 지점을 뽑아 쓰는 것과 달리 플로이드 와샬은 거쳐가는 지점을 중심으로 해서 다시 모든 노드를 탐색한다. 따라서 시간 복잡도는 \(O(N^3)\) 이 걸린다. www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 문제 풀이를 통해 알아보면 시간 복잡도가 높은 만큼 입력 범위는 작게 1..

Bellman - Ford 알고리즘은 다익스트라 알고리즘과 달리 모든 노드를 주기적으로 갱신시켜주기 때문에 \(O(V*E)\)가 걸리지만 음의 가중치를 포함한 노드들에 대해서도 성공적으로 탐색할 수 있다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 대표적인 벨만 - 포드를 사용한 문제이다. 우선 각 간선의 수만큼 입력을 받는데 편하게 계산하기 위해 좌표들에 -1씩 해서 받아줬다. cin >> ..

여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이 바로 순열과 조합인 걸 느끼고 정리를 해보려 한다. 중복을 포함하지 않는 순열 중복을 포함한 순열 중복을 포함하지 않는 조합 중복을 포함한 조합 이렇게 4가지로 나눌 수 있을 것 같다. 각각의 방법에 대해서 DFS와 c++의 algorithm 헤더 파일의 next_permutation을 사용해서 만들 수 있다. 모든 순열과 조합에 대해서 n개 중에서 m개를 뽑는 경우의 수를 보자. 중복을 포함하지 않는 순열(DFS) #include using namespace std; int ar[10], n, m; bool vis[10]; void DFS(int cnt) { if (cnt == m) { for (int i = 0; i < m..

이번에는 다익스트라 알고리즘을 공부해 봤다. 사실 다익스트라는 너무 잘 알려진 알고리즘이라 다른 여러 블로그들을 참고해서 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 이 문제를 푸는 식으로 알아봤다. const int INF = 1e9; vector ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치 vector d; // 거리값을 갱신해주는 배열 일단 기본적으로 가중치..

백준 문제를 풀던 중 약수에 대해 공부할 기회가 생겨 찾아보던 중에 에라토스테네스의 채와 같이 제곱근의 형태를 띄는 최적화를 알게 되었다. for (int i = 1; i