Algorithm/플로이드

[틀림] 프로그래머스 순위 // 플로이드

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 플로이드 학습3중 for문으로모든 정점 쌍의 최단거리를 구함O(n^3) * 풀이명제i가 k를 이기고, k가 j를 이기면i는 j를 이긴다.j는 i에게 진다.승부가 났는지 판단본인제외한 다른사람과 모두 승패를 겨루어 봤는지 확인( 표에 값이 채워져있어야함)#include using namespace std;int graph[104][104];int ret;int solution(int n, vector> results) { for( auto..

[Algo] 플로이드 c++

* 언제 사용?모든 정점간의 최단거리를 구할때 사용시간복잡도 : O(n^3), n=100일때가 정해. n=1000일때도 비빌수는 있음.인접리스트보다는 행렬이 유리!다익스트라 : 한시작점에서 다른 모든 정점의로의 최단거리 구하는 알고리즘 / O(V ElgE) * 의사코드3중 for문을 돌면서정점 k를 하나씩 추가해가면서 이걸 거쳐서 가는게 싼지 탐색k의 for문은 맨 밖에 둬야함에 주의.연산이 대입보다 빠르기때문에, min보다는 if(d[i][j] > d[i][k]+d[k][j]) 인경우 대입하도록 바꾸면 n=1000도 비빌수있음. * 전체코드#include using namespace std;typedef long long ll;int INF = 0x3f3f3f3f;int d[105][105]; //i에..