그린푸딩

처음에 풀었을때 시간초과가 났었다. 푼 방식은 모든 간선(인접리스트로 구현) 을 하나씩 빼서 다시 인접리스트를 새로 만들고 다익스트라를 해보고 지연 시간을 측정하는것이었다.시간초과를 어떻게 줄일까 고민하다가 그래프를 인접행렬로 해야하면 새로 그래프 만들 필요 없어져서 줄어드려나? 했는데 이걸로도 부족했다.지문을 다시 보면 쓸데없는 간선을 삭제해봤자 도둑이 그 경로로 안가면 지연시간이 생길리가 없다.지문에 힌트가 있었다.사실 다른 블로그 힌트 봄..그래서 최단경로를 역추적해서 그 경로상의 간선 각각을 없앤 경우만 최단경로 시간을 구해서 지연시간을 계산하니까 시간초과가 해결되었다. 역시 골드 1인 이유가 있었다..#include#include#include#define INF 100000000using na..

다익스트라 시간복잡도 : ElogV (연결된 정점 탐색 x 가장가까운 지점 정렬) 다익스트라 주의점: 음의 가중치가 있을때 무한 사이클이 생길수 있음#include#include#include#define INF 100000000using namespace std; typedef pair ci; vector dijkstra(vector>&graph, vector&dist,int start) { priority_queue, greater>pq; dist[start] = 0; pq.push({ 0,start }); while (!pq.empty()) { int w = pq.top().first; int e = pq.top().second; pq.pop(); if (dist[e] (w + nw)..

푸는데 오래걸렸다.. 실버인데 못풀어? 이러면서 오른쪽 방향으로 가로/세로/우상향/우하향 을 탐색하는데 주의할것은 지금 위치 전이나, 지금 위치에서 5번째 떨어진곳에 자신과 같으면 안된다. #include #include using namespace std; int arr[20][20]={0}; int dr[4]={0,1,1,-1}; int dc[4]={1,0,1,1}; bool cnt=0; int main() { for(int i=1;iarr[i][j]; } } //연속으로 5개 //6개가 어딘가 있어도 되는가? //6개인데 5개일수도 있잔아 .. //모든 배열에 대해 탐색 for(int i=1;i

최단거리 역추적 문제 #include #include #include #include using namespace std; typedef pair ci; priority_queuepq; int main() { int n,m; cin>>n>>m; vectorarr(n+1,vector()); vectordist(n+1,100000000); vectorway(n+1,-1); int a,b,c; for(int i=0;i>a>>b>>c; arr[a].push_back({b,c}); } int f,e; cin>>f>>e; pq.push({0,f}); while(!pq.empty()){ int w=pq.top().first; int cur=pq.top().second; pq.pop(); if(w>dist[cur])c..

접근 방식 - 택배를 빨리 내릴수 있는걸 우선으로 담아야 최대한 많이 담을수 있다. 처음부터 끝까지 가서 계속 자리만 차지하는 택배를 없애야하는것.. - 정렬해서 처음-도착 위치에 지금 최대 택배를 몇번 담을수 있는지 차례로 계산한다. #include #include #include #include using namespace std; struct info{ int x; int y; int z; }; bool cmp(info a, info b){ if(a.y==b.y){ if(a.z==b.z){ return a.x>w; int m; cin>>m; int a,b,c; for(int i=0;i>a>>b>>c; t.push_back({a,b,c}); } sort(t.begin(),t.end(),cmp); //..

런타임에러 요즘 왜 자꾸 런타임에러가 뜨지 #include #include #include #include #include using namespace std; typedef tuple tp; priority_queuepq; vectorarr; vectorvisited; mapinfo; int dr[4]={0,0,1,-1}; int dc[4]={1,-1,0,0}; int n,m; vectorparent; int find(int node){ if(parent[node]>m; parent.assign(n+1,-1); arr.assign(n,vector(m,0)); visited.assign(n,vector(m,false)); for(int i=0;iarr[i][j]; } } //섬을 지정하기 int num=..

문제가 이해안되서 잘못 풀었는데 정점은 고정되어있고 턴마다 간선이 줄어드는것이다. 처음엔 간선들 사이에 여러개 트리가 있나? 했는데 그게 아니라 간선이 줄어드면서 똑같이 n개의 정점에 대하여 트리가 되는지 푸는 문제이다. 거기다 처음에 find()함수에 리턴을 = 이아니라 >m>>k; parent.assign(n+2,-1); vectorvisited; visited.assign(n+2,vector(n+2,false)); //간선 없애기 vectorpq; int x,y; for(int i=1;i>x>>y; pq.push_back({i,x,y}); visited[x][y]=true; } vectorans(k,0); int turn=0; //정점을 모두 사용한 트리군 트리가 되기만하면 되는게 아니라 //트리가..

모든 간선간의 거리를 구해서 작은순으로 정렬하고 이미 연결된 수 제외하고 n-v-1개까지 유니온시키기 좌표간 연결은 순번 을 부여해서 사용하면 된다. #include #include #include #include #include using namespace std; typedef tupletp; vectorparent; vectornum; double distance(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int find(int node){ if(parent[node]n>>m; double x,y; parent.assign(n+1,-1); num.assign(n+1,{0,0}); f..

슬라이딩 윈도우 문제 #include #include #include using namespace std; bool find(mapm,vectornum){ if(m['A']p; string t; cin>>t; vectornum(4); //A,C,G,T for(int i=0;i>num[i]; } int left=0; int right=left+p-1; mapm; //초기값 for(int i=left;i=s)break; m[t[right]]++; } cout

#include #include #include using namespace std; int main(){ int n; int x; cin>>n>>x; vectorarr(n); vectorvisited(n,0); for(int i=0;i>arr[i]; } //sort(arr.begin(),arr.end()); int cnt=0; for(int i=0;i