PROGRAMMING/알고리즘
-
Articulation point(단절점) 구하는 알고리즘PROGRAMMING/알고리즘 2024. 7. 8. 10:17
아래 블로그에서 정말 많은 도움을 받았으며, 자세한 설명은 아래 블로그에 모두 있습니다!!!!자세한 설명은 아래 글 참고https://ttl-blog.tistory.com/956 [알고리즘] 그래프 (3) - 연결 요소(Connected Components)와 단절점(Articulation Point)🧐 Connected Components 그래프 $G$ 의 Connected Component 인 $G'$ 은 다음과 같이 정의됩니다. Connected Component $G'$ of $G$ : Maximal connected subgraph of $G$ ✔️ Maximum과 Maximal의 차이 Maximum : 최대를 의미합니다. Maxittl-blog.tistory.com articulation p..
-
(백준 4196번 도미노) (라이님 블로그 대회 알고리즘 따라잡기 22) SCCPROGRAMMING/알고리즘 2024. 7. 4. 10:41
백준 4196번https://www.acmicpc.net/problem/4196 SCC를 푸는 것에 추가해서 SCC 하나를 하나의 노드로 보고 indegree가 0인 SCC의 갯수를 세는 문제! 라이님 블로그에서 풀이를 열심히 공부해서 내 식대로 바꿔보았다.https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220802519976&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 정말 많이 틀렸는데.. 대부분의 문제는 노드를 입력 그대로 받아서 생겼다..(보통 문제에서는 점이 1, 2, 3 ... 으로 주어지지만, 프로그래밍은 0, 1, 2...로 하니까....
-
(라이님 블로그 대회 알고리즘 따라잡기 22) 강한 연결 요소(Strongly Connected Component)PROGRAMMING/알고리즘 2024. 7. 2. 12:09
오늘은 라이님의 강한 연결 요소에 대해 알아보았다. 상세한 내용은 Reference를 참고하면 된다. 라이님이 알려준 알고리즘은 Robert Tarjan의 Tarjan 알고리즘이다.동빈나 선생님의 유튜브와 블로그 글도 매우 큰 도움이 된다!!(솔직히 이 유튜브 영상 없었으면 이해가 엄-청 오래 걸렸을 것 같다 ㅠㅡㅠ) 타잔 알고리즘) 동빈나님의 블로그에서 변수명을 내가 알아보기 쉽게 변경한 코드!#include #include #include #include #include // memesetusing namespace std;constexpr int MAX = 10000;int id = 0, disc[MAX]; // disc[i](discovery)는 노드 'i'가 DFS에 의해 처음 발견된 시기 의..
-
(라이님 블로그 대회 알고리즘 따라잡기 21) 오일러 회로(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를 먼저..