분류 전체보기
-
(백준 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를 먼저..
-
CS236 4장 Maximum Likelihood Learning논문 리뷰/cs236 2024. 6. 14. 11:26
Generative model 복습을 위해 CS236 강의를 듣고 정리해보고자 한다.피피티는 아래 페이지를 참고하면 된다.https://deepgenerativemodels.github.io/ Stanford University CS236: Deep Generative ModelsCourse Description Generative models are widely used in many subfields of AI and Machine Learning. Recent advances in parameterizing these models using deep neural networks, combined with progress in stochastic optimization methods, have ena..
-
(백준 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..
-
CS236 3장 Autoregressive Models 정리논문 리뷰/cs236 2024. 6. 12. 16:02
Generative model 복습을 위해 CS236 강의를 듣고 정리해보고자 한다.피피티는 아래 페이지를 참고하면 된다.https://deepgenerativemodels.github.io/ Stanford University CS236: Deep Generative ModelsCourse Description Generative models are widely used in many subfields of AI and Machine Learning. Recent advances in parameterizing these models using deep neural networks, combined with progress in stochastic optimization methods, have ena..