PROGRAMMING/알고리즘
-
(라이님 블로그 대회 알고리즘 따라잡기 20) 오일러 회로(Eulerian Circuit)PROGRAMMING/알고리즘 2024. 6. 24. 14:20
오늘은 오일러 회로를 공부해보았다. Eulerian이라고 쓰는게 맞는 표현인지 오늘 처음 알았다ㅎㅎ... 늘 그렇듯 오늘도 라이님 블로그를 참고했다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220800097205&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 오일러 경로(Eulerian Path), 오일러 회로(Eulerian Circuit) (수정: 2019-08-20)이번에 소개할 내용은 오일러 경로(Eulerian trail) 및 오일러 회로(Eulerian circuit)입니다. 위상수학,...blog.naver.com 여기 있는 코..
-
(백준 4386번 별자리 만들기) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 18. 11:22
백준 4386번https://www.acmicpc.net/problem/4386 처음에는 스패닝 트리 문제라는 생각이 안 드는 문제.. n개의 별들을 잇는 최소의 거리를 찾는 문제다. n개의 별들 사이의 거리는 주어져 있지 않으므로 $\frac{n \times (n-1)}{2}$의 간선에 대해 길이를 먼저 구해야 한다. 이 중 거리가 최소인 간선부터 이어(일종의 그리디 알고리즘) 최소의 간선 갯수만 이으면 된다. V개의 노드가 있다면 V-1개의 간선을 잇는 것이 최소이기 때문에 자연스럽게 트리 모양이 된다는 것을 알 수 있다. 즉, 가중치의 합이 최소인 트리를 찾는 MST 문제가 되는 것이다! 참고로 double을 사용할 때 %lf를 쓴다는 사실과 소수점 두번째 자리까지만 프린트하는 %.2lf를 까먹어..
-
(라이님 블로그 대회 알고리즘 따라잡기 20) 위상 정렬(Topological Sort)PROGRAMMING/알고리즘 2024. 6. 18. 10:08
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220800013823&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 위상 정렬(Topological Sort) (수정: 2017-06-22)안녕하세요. 이번에도 역시 그래프입니다. 그래프 아직 한창 남았어요. 이번에는 위상 정렬(topological so...blog.naver.com 최소 스패닝 트리와 뭔가뭔가 비슷한 느낌의 알고리즘 그래프의 정점을 정렬하는 방법으로 선수과목이 있는 문제들에서 사용 가능한 알고리즘이다. 라이님의 백준 2623번 문제를 vector를 사용해서 약간만 바꿔보았다. ht..
-
(백준 6497번 전력난) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 17. 10:50
백준 6497번https://www.acmicpc.net/problem/6497 MST를 구해서 총 가중치의 합에서 빼면 되는 문제!MST를 구하기 위해서는 크루스칼 알고리즘을 사용하면 되는데, 크루스칼 알고리즘은 union find와 정렬을 잘 조합한 알고리즘이라서 어렵지 않다! #define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;int uf[200000];int find(int a) { if (uf[a] edges; edges.resize(n); int total = 0; for (int i = 0; i
-
(백준 1647번 도시 분할 계획) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 17. 10:32
최단 거리 찾는 알고리즘 3인방을 끝내고 오늘은 최소 스패닝 트리를 구하는 알고리즘에 대해 알아보았다. 라이님 블로그에 나온 알고리즘은 바로 크루스칼 알고리즘! 정렬 + 유니온 파인드를 이용하면 시간복잡도 O(ElogE)로 구할 수 있다! gpt에게 살짝 수정시킨 알고리즘은 다음과 같다. #include #include #include using namespace std;struct Edge { int u, v, w; bool operator edges; edges.reserve(M); // 메모리 할당 최적화 for (int i = 0; i 위 풀이를 기준으로 1647번을 풀어보았다. 백준 1647번https://www.acmicpc.net/problem/1647 MST를 먼저..
-
(백준 1956번 운동) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 13. 11:23
최단거리 알고리즘 복습 2탄 - 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘이 제일 심플하다..ㅎㅎ 백준 1956번https://www.acmicpc.net/problem/1956 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int arr[400][400]; int V, E; cin >> V >> E; for (int i = 0; i > a >> b >> c; arr[a - 1][b - 1] = c; } for (int k = 0; k
-
(백준 1238번 파티) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/알고리즘 2024. 6. 13. 10:59
최단거리 알고리즘 복습 1탄 - 다익스트라 알고리즘 백준 1238번https://www.acmicpc.net/problem/1238 풀이에 중복이 있어 제거하는 풀이를 chatgpt에게 부탁했는데, 두번째 풀이도 바로 챗gpt 풀이다.(gpt가 틀렸길래 디버깅 좀 했쑴ㅎㅎ) 첫번째 풀이다익스트라 알고리즘을 사용해서 all node -> X로 가는 최단 경로를 구한 후(N-1번의 다익스트라 알고리즘 사용) X -> all node로 가는 최단 경로를 구했다.(1번의 다익스트라 알고리즘 사용) 다익스트라 함수를 구현하는데 있어 겹치는 부분이 많아 아쉬운 풀이 #include #include #include #include #include #include using namespace std;typedef pa..
-
(백준 9205번 맥주 마시면서 걸어가기) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 12. 11:15
플로이드 와샬 알고리즘 문제인지 모르고 봤다면 푸는게 좀 난해했을 것 같은 문제다..! 백준 9205번https://www.acmicpc.net/problem/9205 집과 n개의 편의점, 그리고 축제 장소가 2차원 공간에 있지만 하나의 그래프 노드라고 생각하면 문제가 쉽게 풀린다!두 점 사이의 맨해튼 거리가 1000이 넘으면 맥주가 부족해 도착하지 못하므로 1000을 기준으로 각 노드들(집, 편의점, 축제 장소)가 이어져 있는지를 우선 dist matrix에 0과 1을 이용해 표시한다. 다음 플로이드 마샬 알고리즘을 이용해 집에서 축제 장소까지 연결된 루트가 있는지 확인해주면 끝! 대칭(symmetric matrix)이기 때문에 distance matrix와 플로이드 와샬 알고리즘을 upper tria..