정화 코딩

서론처음이자 마지막으로 나가는 ICPC이다. 졸업하기도 하고 나이도 그렇고 올해가 마지막 기회다. PS를 시작한 건 최근은 아니지만 열심히 하기 시작한 게 최근이라서 뉴비라고 적었다. 1년도 안 된 것 같다. 사실 딱히 열심히도 아닌 것 같기도... 하핫 1년은 무슨 반년 정도 되는 것 같넹 작년에는 ICPC에 관심이 없었던 것 같다. 암튼 열심히 하다 보니 나가고 싶어져서 팀을 만들었다.팀은 celina324, g_grain, jungh150 이렇게 구성되어 있고, 지지난번 SUAPC에도 이렇게 나갔던 것 같다. 워낙 은채랑 지은이 둘 다 학교에서 잘하는 편이기 때문에 1등을 못할 것 같다는 생각은 없었고, 그래서 가장 중요한 건 학교 별 1등 커트라인 넘기기였다. 그래서 골드 다 풀기를 목표로 계속 ..

https://www.acmicpc.net/problem/11408 기본적인 최대 유량 문제 풀듯이 하되, 각 단계마다 현재 잔여 그래프에서 최단 거리 알고리즘을 이용해 최소 비용 증가 경로를 찾고, 그 경로로 유량을 흘려준다. 최단 거리를 구할 때는 벨만 포드 알고리즘을 약간 변형시켜 평균 실행 시간을 줄인 SPFA를 사용하였다. // Reference: green55 teamnote// https://github.com/green5555/Teamnote/blob/master/TeamNote/MCMF.cpp#include using namespace std;typedef long long ll;typedef pair pll;//O(VEf), Average = O(Ef)const int MAX=2010;..

https://www.acmicpc.net/problem/11377 이렇게 중간 노드를 하나 만들어서 거기로 k만큼 흘려주도록 모델링하면 이렇게 된다. // Reference: green55 teamnote// https://github.com/green5555/Teamnote/blob/master/TeamNote/Ed-Karp.cpp#include using namespace std;typedef pair pii;const int MAX = 2010, INF = INT_MAX;struct maxflow { struct edge { int next, cap, flow = 0, rev_idx; edge() {} edge(int n, int c) : next(n)..

https://www.acmicpc.net/problem/5419 스위핑 아이디어우리가 하고 싶은 것: 각 섬마다 자신보다 북서쪽에 있는 섬들이 몇 개인지 -> 그것들의 합을 구하면 정답그러므로 섬들을 x 기준 오름차순, y 기준 내림차순으로 정렬해두자.그렇게 정렬해둔 다음에, 앞에서부터 보면서 각 섬 기준 북서쪽에 있는 섬들이 몇 개인지 셀 때 지금까지 본 섬 중 자기보다 y값이 크거나 같은 섬이 몇 개였는지만 세면 된다.자기 기준으로 북서쪽 섬이 몇 개인지 확인 후, 자기 섬도 등록해야 한다. 세그먼트 트리 아이디어지금까지 본 섬들 중 자기보다 y값이 크거나 같은 섬이 몇 개인지를 빠르게 구하기 위해서 세그먼트 트리를 사용해야 한다.-> 세그먼트 트리에 저장해야 하는 값: 지금까지 본 섬들의 y값 분..

https://www.ecva.net/papers/eccv_2024/papers_ECCV/papers/08071.pdfhttps://arxiv.org/abs/2407.01851 Meerkat: Audio-Visual Large Language Model for Grounding in Space and TimeLeveraging Large Language Models' remarkable proficiency in text-based tasks, recent works on Multi-modal LLMs (MLLMs) extend them to other modalities like vision and audio. However, the progress in these directions has been ..

https://www.acmicpc.net/problem/4196 첨엔 그냥 scc 개수를 구해서 틀렸다. 그런데 1과 2가 같은 scc이고 3과 4가 같은 scc이면서 2에서 3으로 가는 간선이 있는 경우를 생각해보면, scc 개수는 2이지만 답은 1이다.왜냐하면 1을 넘어뜨리면 같은 scc인 2도 자연스럽게 넘어지고 따라서 3, 4도 넘어지기 때문이다. 따라서 이 문제는 scc를 구한 뒤, in-degree가 0인 (다른 것에 의해서 넘어지지 않는) scc의 개수만을 세야 한다. #include #include #include using namespace std;vector> adj1;vector> adj2;vector vst;stack stk;vector scc;int idx;void dfs1(in..

강한 연결 요소 - Strongly Connected Component (SCC)방향 그래프에서 모든 정점 쌍 사이에 경로가 존재할 때, 그 그래프는 강하게 연결되어 있다고 한다.방향 그래프에서 모든 정점 쌍 사이에 경로가 존재하는 최대 부분 그래프를 강한 연결 요소라고 한다. Kosaraju 알고리즘: scc를 구하는 알고리즘adj1: 원래 방향 그래프의 인접 리스트adj2: 원래 그래프의 간선을 모두 반대로 뒤집은 그래프의 인접 리스트dfs1: 원래 그래프를 dfs로 탐색함. 탐색하면서 완료 정점을 stack에 담음.dfs2: stack의 정점들을 pop하면서 반전 그래프를 dfs로 탐색함. => dfs2 호출 횟수가 강한 연결 요소 개수 #include #include #include #includ..

https://www.acmicpc.net/problem/3295 그래프의 구조가 링이거나 선형 배열이라는 것은 그래프를 이루는 각 노드들의 in-degree도 최대 1이고 out-degree도 최대 1이라는 것이다. 그리고 k개의 노드로 이루어진 링의 가치가 k이고 k개의 노드로 이루어진 선형 배열의 가치가 k라는 것은 어떤 그래프에서 각 노드의 in-degree도 최대 1이고 out-degree도 최대 1이 되도록 간선들을 선택했을 때의 간선 개수 자체가 가치가 된다는 뜻이다. 따라서 왼쪽에 출발 노드 집합을 두고 오른쪽에 도착 노드 집합을 두고 최대 이분 매칭을 구하면 된다. // Reference: green55 teamnote// https://github.com/green5555/Teamno..