fatalite

문제 문제 난이도 : 골드 4 문제 분류 : 다익스트라 문제 코드 #include #include #include #include #include #include #include #include using namespace std; int Distance[3000]; vector Edges[3000]; const int MYINTMAX{ 2140000000 }; bool Visited[3000]; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout.tie(NULL); } void Dijkstra(int s, int e) { for (int i = 0; i < 3000; i++) { Distance[i] = MYINTMAX; }..

문제 문제 난이도 : 골드 3 문제 분류 : 위상 정렬(Topology Sort) 문제 리뷰 Keyword : 진입 차수, Queue 진입 차수 배열 작성 (Loop) 진입 차수가 0인 것들을 선택하면서(이 과정에서 위상 정렬의 순서는 단일 되지 않게 됨) 출력한다. (Loop) pop된 부분이랑 연결된 노드의 진입 차수를 감소시킨다. 위상 정렬 어려울 줄 알았는데 간단하고 명료하다.. 문제 소스 코드 #include #include #include #include #include #include #include #include using namespace std; vector Edges[32001]; void Init() { ios_base::sync_with_stdio(false); cin.tie(N..

문제 문제 난이도: 골드 4 문제 분류: 최소 스패닝 트리 문제 리뷰 최소 스패닝 트리!!! 그리디를 이용한다. 그리디를 이용하기 위해서 유니온 파인드 알고리즘(경로 압축, 랭크 압축을 필요시 추가 구현해야한다. 난 여기서 경로 압축만 쉬워서.. 구현했다)을 사용(트리로 구현, 배열로 구현하는 방법도 있음.)한다. 내일은 프림 알고리즘을 배워보자꾸나 문제 난이도 #include #include #include #include #include #include #include #include #include using namespace std; //Global Variable vector Edges; int RootNode[1001]; int NodeNum, EdgeNum; //Initializing for..

문제 문제 난이도 : 골드 3 문제 분류 : 최소 스패닝 트리(Minimum Spanning Tree) 문제 리뷰 약간의 기하(초등)와 MST가 합쳐진 문제다. double 자료형에 precision을 소수점 두자리까지 출력해야해서 골드 3으로 책정된 듯 하다. 문제 소스코드 #include #include #include #include #include #include #include #include using namespace std; vector Edges; int Root[1001]; int n; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout.tie(NULL); } int Find(int x) { if (Root[..

문제 문제 난이도 : 골드 4 문제 분류 : 다익스트라 문제 리뷰 딱히.. 없지만.. memset 이거 왜 작동 잘 안하는지 모르겠다. 제대로 다시 알아보자,, 문제 소스 코드 #include #include #include #include #include #include #include #include using namespace std; vector Edges[16000]; int Distance[16000]; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout.tie(NULL); } void Dijkstra(int start) { for (int i = 0; i < 16000; i++) { Distance[i] = 210..

문제 문제 난이도 : 골드 4 문제 분류 : 다익스트라 알고리즘 문제 리뷰 다익스트라를 정복해보자아 다익스트라는 Greedy + DP 이며, 시간 복잡도는 NlogN(우선 순위 큐를 썼을 경우) 문제 소스코드 #include #include #include #include #include #include #include #include #include using namespace std; //Global Variable vector Edges[10010]; int Distance[10010]; //Initializing for Optimization void Init() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } void Dijkst..

문제 문제 난이도 : 실버 1 문제 분류 : Graph , DFS, BFS 문제 풀이 및 코드 #include #include #include #include #include #include using namespace std; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int main() { //Initialize Init(); //Input int W, H; cin >> H >> W; vector Map(H, vector(W,false)); vector Visited(H, vector(W, false)); for (int i = 0; i > s; for..

Problem 실버 2 문제 분류 그래프 탐색 문제, 트리 접근 DFS(탐색용), Adj List(V = E), 무방향 그래프 표현, 구조체 이용 몰랐던 것 및 까먹은 부분 1) 트리에는 루트 노드가 원래 없다. 2) "\n" 3) ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Solution #include #include #include using namespace std; int n; struct node { int parent = -1; bool visited = false; vector linked; }; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ..