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.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
1761 정점들의 거리
https://www.acmicpc.net/problem/1761 트리에서의 두 정점 사이의 경로는 하나만 존재하므로 경로 사이의 거리가 곧 최단 거리가 된다. 이 점을 이용하여 루트에서 부터의 정점 i까지의 거리를 d[i]라 하면 두 정점 u,v 사이의 거리는 d[u]+d[v]에서 경로에 해당되지 않는 부분인 d[lca(u,v)]가 두 번 포함되었으므로 dist(u,v)=d[u]+d[v]-2*d[lca(u,v)] 이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include #include using namespace std..
https://www.acmicpc.net/problem/11437 트리에서 두 노드의 LCA (Lowest Common Ancestor), 즉 가장 가까운 공통 조상을 찾는 문제이다. Naive한 방법으로 O(N)만에 구할 수 있다. 모든 노드를 루트에서 시작하여 BFS (Breadth First Search)로 탐색하여 모든 노드의 부모와 깊이를 구한다. 그리고 LCA를 구하고자 하는 두 노드 중 더 깊은 노드를 올려서 두 노드의 깊이를 똑같이 맞춰준다. 그리고 하나씩 동시에 올리면서 처음 두 노드가 같아졌을 때 그 노드가 LCA이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..
https://www.acmicpc.net/problem/4150 string의 + 연산을 연산자 오버로딩(Operator Overloading)하여 큰 수 연산을 구현하였다. 123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std; string operator+(string &a,string &b){ string ret; int s1=a.size(),s2=b.size(),up=0; for(int i=s1-1,j=s2-1;(i>=0||j>=0);i--,j--) { int d; if(i>=0 && j>=0) d=a[i]-'0'+b[j]-'0'+up; else if(i>=0 && j