https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE 유니온 파인드를 구현하자. 123456789101112131415161718192021222324252627#include int p[1000001];int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }void Union(int x,int y) { p[Find(x)]=Find(y); } int main(){ int t; scanf("%d",&t); for(int k=1;k
https://www.acmicpc.net/problem/14716 DFS나 BFS를 이용하여 연결 요소(Connected Component)의 개수를 세준다. 1234567891011121314151617181920212223242526#include int m,n,map[250][250],ans;int dx[8]={-1,-1,-1,0,0,1,1,1};int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(int x,int y){ map[x][y]=0; for(int i=0;i
https://www.acmicpc.net/problem/1213 팰린드롬(Palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 예를 들면 abba, abbba, abcdcba 등이 팰린드롬이다. 이 문제는 문자열이 주어지고 적절히 위치를 바꿔서 팰린드롬을 만들 수 있는지 확인하는 문제이다. 1. 길이가 짝수이면 모든 알파벳의 개수도 짝수여야 한다.2. 길이가 홀수이면 하나의 알파벳의 개수만 홀수여야 한다. 위의 조건을 만족하는지 확인하고 팰린드롬을 만들 수 있다면 사전 순으로 출력한다. 먼저 A~Z까지 순서대로 보면서 개수의 절반씩 출력하고 다시 거꾸로 Z~A까지 보면서 나머지 절반을 출력하면 사전 순이 됨을 알 수 있다. 길이가 홀수인 경우는 미리 해당 인덱스를 저장한 후..
https://www.acmicpc.net/problem/7507 그리디(Greedy) 알고리즘으로 해결할 수 있다. 경기가 빨리 끝나는 순으로 하나씩 본다면 최적해가 보장됨을 알 수 있다. 1234567891011121314151617181920212223242526#include #include using namespace std; struct G { int d,s,e; };G g[50000];int n,m;bool cmp(G &g1,G &g2) { return g1.d!=g2.d?g1.d
https://www.acmicpc.net/problem/1005 위상 정렬으로 해결할 수 있다. 한 정점에 연결되어 있는 이전의 모든 정점들 중 건설 시간이 가장 긴 정점이 최종적으로 현재 정점의 건설 시간에 영향을 준다. 따라서 이를 메모이제이션(Memoization) 하면서 갱신해간다. 최종적으로 indegree가 0인 시점에서 해당 정점이 건설해야 할 건물이면 그 정점의 d 배열값이 정답이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using namespace std; int t,n,k,x,y,w,ind[1001],time[..
https://www.acmicpc.net/problem/6086 네트워크 플로우(Network Flow) 문제이다. 에드먼드-카프(Edmond-Karp) 알고리즘을 이용하여 A에서 Z까지의 최대 유량을 구한다. BFS로 증가 경로(Augmenting Path)를 찾아주면서 해당 경로상의 잔여 용량(Residual Capacity)의 최소값을 구한다. 그리고 유량의 대칭성을 유지하기 위해 유량을 보내는 방향의 간선들의 유량을 최소값만큼 늘리고 반대 방향의 간선들의 유량은 감소시킨다. 이 과정을 증가 경로를 더 이상 구하지 못할 때까지 반복하면 최대 유량을 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142..
https://www.acmicpc.net/problem/1516 위상 정렬(Topological Sort)은 DAG(Directed Acyclic Graph), 즉 사이클이 없는 유향 그래프에서 Indegree가 0인 정점들을 하나씩 제거해 가면서 정렬하는 알고리즘이다. 위상 정렬을 이용하여 선후 관계를 고려하면서 각 건물이 완성되기까지 걸리는 최소 시간을 구할 수 있다. 스타크래프트를 예로 들자면 스타포트를 올리기 까지의 최소 테크트리는 배럭->팩토리->스타포트이고 템플러 아카이브를 올리고 싶다면 게이트웨이->사이버 네틱스 코어->시타델 오브 아둔->템플러 아카이브 순으로 지어야 한다. 이 때 한 정점 이전에 연결되어 있는 정점들이 여러개 있다면 그 중 가장 시간이 오래 걸리는 것이 최종적으로 다음 ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf Core의 개수가 최대 12개 이므로 각각의 Core에 대해서 4가지 방향의 모든 경우의 수를 만들면 된다. 최대 4^12=16777216 이므로 시간 초과에 대해서는 걱정할 필요가 없음을 알 수 있다. 각 경우에 대해서 가장자리에 있는 코어는 어차피 전원에 연결되 있으므로 따로 카운트 해주고 나머지 코어들에 대해서 정해진 방향으로 전선을 만들어 보면서 기존의 코어나 전선과 겹치는 것이 없는지 확인한다. 그리고 정답을 갱신해 갈 때 Core의 개수, 전선 길이의 합 순으로 우선순위를 두어서 한다. 또한 테스트케이스가 여러 개이므로 ..
https://www.acmicpc.net/problem/9657 이기는 위치의 값을 1, 지는 위치의 값을 0이라고 하면 다음 턴을 하나라도 지는 위치로 만들 수 있다면 현재 위치가 이기는 위치이고 다음 턴의 모든 경우가 이기는 위치라면 현재 위치가 지는 위치가 된다. 12345678910111213141516#include int n,d[1001]; int main(){ scanf("%d",&n); for(int i=1;i=0 && !d[i-1]) d[i]=1; if(i-3>=0 && !d[i-3]) d[i]=1; if(i-4>=0 && !d[i-4]) d[i]=1; } printf("%s",d[n]?"SK":"CY"); return 0;}cs
https://www.acmicpc.net/problem/10775 큰 번호의 게이트부터 도킹해야 최대한 많은 비행기를 도킹할 수 있다. 파인드 연산을 통해 이미 도킹했다면 앞의 게이트와 연결 시켜서 다음 도킹할 자리를 빨리 찾을 수 있다. 파인드 연산 결과가 0이라면 더 이상 도킹할 자리가 없으므로 종료 시켜주면 된다. 12345678910111213141516171819#include int n,m,t,c,r,p[100001];int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } int main(){ scanf("%d %d",&n,&m); for(int i=1;i