반응형 C++153 [알고리즘] c++ cpp 카펫 포인트 1. 머리를 조금 굴릴 필요가 있다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; for(int i = yellow ; i >= (yellow/i) ; i--){ if (yellow%i != 0) { continue; } if (((2*i)+(2*(yellow/i))+4) == brown) { answer.push_back(i+2); answer.push_back((yellow/i)+2); break; } } return answer; } 2020. 10. 23. [알고리즘] c++ cpp 네트워크 연결 포인트 1. mst 를 잘 이해할 수 있는가를 묻는 문제 (mst 는 크루스칼 알고리즘, 프림 알고리즘 등이 있다. ) 크루스칼 알고리즘이 빠르긴하다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 프림 알고리즘 #include #include #include #include using namespace std; int n, m; bool visited[1001]; vector map[1001]; //가중치, 목적지 priority_queue pq; //가중치기준 최소힙 int prim() { int ans = 0; pq.push({0, 1}); while (!pq.empty()) { int cost, x; tie(cost, x) = pq.top(); pq.pop(); if (visited[x.. 2020. 10. 23. [알고리즘] c++ cpp 지형 이동 포인트 1. bfs, 프림 알고리즘을 섞는다. bfs 는 구역의 이름을 짓기위하여 실행을 한다 프림은 mst 를 구하기 위하여 실행을 한다. 2. 아직 이 문제는 어렵다. 억지로 풀기는 하였다 그래도 중요하다고 생각을 하는 부분은 중간에 있는 calc 함수라고 생각을 한다. calc 를 통해서 맵을 돌면서 인접 섹션이 다른 것들을 노드로 하고 이를 도는 mst 를 만드는 생각이 중요한 것 같다. 프림은 아무리 여러개가 연결이 되어 있어도 결국은 하나의 경로를 택하기 때문에 따로 처리는 상관이 없다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; int section[301][301]; int visited[301][301];.. 2020. 10. 23. [알고리즘] 섬 연결하기 포인트 섬을 연결을 하는 방법은 무엇인가? 모든 섬이 최소 비용으로 연결되어 있어야 한다. 최단거리가 아님을 인지하자 (최소 비용으로 연결된 MST 를 구하는 문제이다. ) 결국은 연결되는 cost 를 전부 더해주는 것입니다. MST 를 구하는 알고리즘은 크루스칼(union, find 를 사용합니다), 프림 등이 있다. (저는 프림을 애정합니다. ) 시간 복잡도 O(n^2) 을 가지고 있다. c++ 에서는 우선 순위 큐에서 greater 를 통해서 만들 수 있고, python 은 heapq 모듈을 통해서 만들 수 있다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 프림 알고리즘(min_heap 을 이용하여 구현) #include #include #include #include using na.. 2020. 10. 23. 이전 1 ··· 16 17 18 19 20 21 22 ··· 39 다음 반응형