본문 바로가기

알고리즘 관련

advanced disjoint set 오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동.. 더보기
BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기
BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 더보기
BOJ)2171 직사각형의 개수 문제: icpc.me/21712차원 평면위에 5000개 이하의 점이 있을 때 점들로 만들 수 있는 모든 직사각형의 수를 세는 문제이다,n제한이 5000에 2초이므로 n^2logn 솔루션으로 풀 수 있을 것이라고 생각하였다.n*n으로 모든 두 점에 대하여 직사각형의 대각선에 놓이는 경우를 생각하면, 나머지 대각선에 포함되는 두 점은 set을 이용해 존재여부를 log시간에 찾을 수 있다.123456789101112131415161718192021222324252627#include #include #include #include using namespace std;int n,res;set st;vector vt;int main(){ scanf("%d",&n); for(int i=0;i 더보기
BOJ)14943 벼룩 시장 문제: icpc.me/14943벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.1234567891011121314151617181920212223242526272829303132333435363738#include #inclu.. 더보기
BOJ)14950 정복자 문제:icpc.me/14950모든 도시를 점거하는데 필요한 최소 비용을 출력하는 문제이다.단 도시를 점거 해 나갈 때 마다 일정 비용이 추가 되었는 데 이것에 포커스를 맞추면 문제가 어려워 질 수 있다.조금 생각을 해보면 결국 모든 도시를 점거해야하기 때문에 MST를 만들어주면 비용을 커버할 수 있는 걸 알 수 있다.이미 MST를 구상하였다면 이에 이용 된 간선은 n-1개로 고정일 것이고, 이는 모든 도시를 점거하는데 필요한 간선의 최소 개수이기도 하기 때문에(1~n-1 까지의 합) x t가 증가하는 비용으로 고정된다.123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using nam.. 더보기
BOJ)15271 친구 팰린드롬2 문제: icpc.me/15271남자와 여자에 대한 이분 그래프가 형성되므로 이분 매칭으로 최대로 세울 수 있는 친구 수를 구해줄 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;int n, m, visited[222], b[222];vector vt;int dfs(int here) { if (visited[here])return false; visited[here] = true; for (auto next : vt[here]) { if (!b[next] || dfs(b[next])) { b[next] = .. 더보기
BOJ)15270 친구 팰린드롬 문제: icpc.me/15270 명시 된 N의 범위가 작으므로 상태DP를 이용하여 해결할 수 있다.dp[state][pos] = state(이미 친구가 된 사람들의 상태를 표현)이고 pos번째 까지 친구 관계를 봤을 때 춤을 추는 인원의 최댓값12345678910111213141516171819202122232425262728#include #include #include using namespace std;int dp[1 더보기
BOJ)14939 불 끄기 문제: icpc.me/14939 언제 봤는지는 기억이 잘 안 나지만 언젠가 한번 봤었던 은근히 well-known 문제이다.첫 줄에 전구를 어떤 방식으로 뒤집는 걸 결정을 했다고 가정하면 그 아래 줄은 바로 위의 전구가 켜져 있는지 여부에 따라서 뒤집기 결정을 그리디하게 할 수 있다.따라서 첫 줄을 뒤집는 모든 경우 (2^10)에 대하여 정해준 뒤, 그리디하게 뒤집어주어 최적의 답을 구하는 것이다. 비슷한 시기에 나온 홍익대학교 경시대회의 전구 끄기 문제도 한번 풀어보면 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #incl.. 더보기
BOJ)14938 서강그라운드 문제: icpc.me/14938 n의 범위가 작고 다대다 최단거리를 필요로 하기 때문에 플로이드 워셜 알고리즘을 사용할 수 있다.플로이드 워셜 알고리즘으로 모든 정점쌍의 최단거리를 구해준 후 , 모든 정점을 기준으로 얻을 수 있는 아이템의 개수를 세준 뒤 그 중에 최댓값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, m, r, item[111], a[111][111], res;int main() { memset(a, 0x3f, sizeof(a)); scanf("%d%d%d", &n, &m, &r); for (int i = 1.. 더보기

티스토리툴바