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 여기 있는 코..
-
cs236 5-6장 Latent Variable Models(VAEs)PROGRAMMING/머신러닝 2024. 6. 20. 20:55
Generative model 복습을 위해 CS236 강의를 듣고 정리해보고자 한다.피피티는 아래 페이지를 참고하면 된다.https://deepgenerativemodels.github.io/ ※ PPT의 내용 정리와 더불어 같이 보면 좋을 자료들을 정리했습니다. 강의를 보고 이해한대로 작성했기 때문에 부정확한 내용이 포함되어 있을 수 있음을 알려드립니다. 또한 참고한 모든 블로그와 유튜브는 출처(Reference)에 있습니다. Latent Variable Models : Motivation사람의 얼굴을 생각해보자. 눈의 색깔, 머리의 색깔, 포즈, 성별 등등 다양한 factor들로 사람의 얼굴을 결정할 수 있다. 이때의 다양한 팩터들을 사람이 직접 정하지 않고 latent variable로 나타내보고자..
-
Importance Sampling(중요도 샘플링)PROGRAMMING/머신러닝 2024. 6. 19. 16:22
Importance Sampling은 Monte Carlo Simulation을 할 때 variance를 줄여주는 중요한 테크닉 중 하나다.Importance Sampling을 ELBO를 증명하는데도 사용하길래 간단하게 정리해보았다.Importance SamplingImportance sampling은 probability measure를 바꾸므로써 Monte Carlo simulation에서의 variance를 줄이는 하나의 테크닉이다. Importance Sampling은 더 중요한 결과에 높은 가중치를 줌으로써 샘플링의 효율성을 높인다. 확률 변수 $X$의 확률 밀도 함수 $f$에 대해 $h(X)$의 기댓값은 다음과 같이 쓸 수 있다. $\alpha = E[h(X)] = \int h(x)f(x) d..
-
(백준 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 LearningPROGRAMMING/머신러닝 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..