지우너

문제https://www.codetree.ai/missions/8/problems/pair-of-points-that-can-be-moved?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 문제 쪼개기주어지는 것1부터 N까지 번호가 붙은 N개의 서로 다른 점이 점들 중 임의의 두 점을 잇는 M개의 길N개의 점 중 1번부터 P번까지의 점은 빨간점 조건 모든 길은 한 방향으로만 이동(방향 그래프)특정 두 점을 잇고 특정 방향으로 이동 가능한 길은 최대 1개만 존재(중복 간선은 주어지지 않음)..

문제https://www.codetree.ai/missions/8/problems/shortest-distance?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 코드#include using namespace std;const int MAX_N = 101;int n, m;int dist[MAX_N][MAX_N];int main() { //input cin >> n >> m; for(int i=1; i> dist[i][j]; } } // soluti..

문제https://www.codetree.ai/missions/8/problems/shortest-path-to-each-vertex-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 코드#include using namespace std;const int MAX_N = 101;int n, m;int dist[MAX_N][MAX_N];void InitDist(){ for(int i=1; i> n >> m; InitDist(); for(int i=0; i> v1 >> v2..

문제https://www.codetree.ai/missions/8/problems/shortest-distance-9?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai   경로를 저장할 path[]배열 만들기path[i]에는 시작점으로부터 i번째 정점에 최단거리로 도달하기 위한 바로 직전 노드의 번호가 적히게 됩니다.도착지점부터 path배열 역추적(stack) 문제가 1-based인데, -1해서 저장하고 0-based로 풀고 마지막에 +1해서 출력하는 게 더 복잡한 거 같아서 그냥 1-ba..

그래프의 가중치가 없거나, 모든 간선의 가중치가 동일하다면 BFS를 이용하여 최단거리를 구할 수 있다.왜 쓰는가?그런데 가중치가 다를 경우, BFS를 이용하여 최단거리를 구하는 데에 어려움이 있다.이를 해결하기 위해 나온 알고리즘 중 하나가 다익스트라 알고리즘 언제 쓰는가?어떤 점에서 다른 모든점으로 가는 최단거리를 구할 때1~5까지의 점이 있고, 1에서 출발한다고 가정. 1-2의 최단거리, 1-3의 최단거리, 1-4의 최단거리, 1-5의 최단거리를 구할 수 있다는 의미 어떻게 쓰는가?기본 개념어떤 정점에서 시작해서 각 정점으로 가는 최단 거리를 구해야 한다. dist를 저장할 자료구조를 선택하고 시작 정점을 0, 나머지 정점을 inf로 초기화한다.(3번에서 시작한다고 가정했을 때, 3번으로 가는 최단거..

문제https://www.codetree.ai/missions/8/problems/shortest-path-to-each-vertex?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 코드#include #include #include using namespace std;const int MAX_N = 20001;int n, m, k; // 정점의 수, 간선의 수, 시작 정점vector > graph[MAX_N];priority_queue, vector >, greater> pq; // {..