반응형 분류 전체보기272 [알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질1) 포인트 1. BFS (너비 우선 탐색) 2. 기본적인 것들은 똑같고 조건들만 다름을 이해하자 #include #include using namespace std; #define MAX 100001 bool visited[MAX]; int n, m; int bfs() { queue q; int time = 0; q.push(n); while (1) { int size = q.size(); for (int i = 0; i 0 && !visited[n - 1]) { //범위체크 && 방문하지 않았거나 q.push(n - 1); visited.. 2020. 10. 4. [알고리즘] c++, cpp 플로이드 와샬 모드 정점에서 모든 정점까지 최단 거리를 구한다. 복잡도 O(n^3) 포인트 1. 다익에스트라는 한 정점, 플로이드는 모든 정점에서 #include #include using namespace std; #define INF 987654321 #define ARR_SIZE 100 + 1 int node, edge; int map[ARR_SIZE][ARR_SIZE]; int start, arrive, weight; void floyd_warshall() { for (int i = 1; i > edge; for (int i = 1; i start >> arrive >> weight; if (map[start][arrive] > weight) map[start][arrive] = weight; } floyd_w.. 2020. 9. 26. [알고리즘] c++, cpp 다익스트라 (한 정점에서 최단 거리) 포인트 1. 한 정점에서 최단 거리를 구하는 알고리즘 2. 음수의 경우는 사용을 할 수 없다. 3. 우선 순위 큐에서 min heap 을 구현을 하여 사용한다. #include #include #include using namespace std; int n, m; int s, e, c; int start, arrive; int dist[1001]; vector map[1001]; int main() { cin >> n >> m; for (int i = 0; i > s >> e >> c; map[s].push_back({c, e}); // 도시 간 연결 정보 } cin >> start >> arrive; for (int i = 1; i cost + ncost) // 다른 도시.. 2020. 9. 26. [알고리즘] c++, cpp 소수 찾기 포인트 1. 에라토네스 체, 소수 판별하는 방법 2. 조합을 구하는 방법 #include #include #include using namespace std; bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i*i 2020. 9. 26. 이전 1 ··· 60 61 62 63 64 65 66 ··· 68 다음 반응형