그린푸딩

문제가 이해안되서 잘못 풀었는데 정점은 고정되어있고 턴마다 간선이 줄어드는것이다. 처음엔 간선들 사이에 여러개 트리가 있나? 했는데 그게 아니라 간선이 줄어드면서 똑같이 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

목록을 set에 저장해서 번호 부여해서 유니온 파인드 #include #include #include #include using namespace std; vectorparent; int find(int node){ if(parent[node]t; while(t--){ sets; cin>>n; string a,b; vectorarr; for(int i=0;i>a>>b; arr.push_back({a,b}); s.insert(a); s.insert(b); } mapnum; //번호 부여 int cnt=1; for(auto it=s.begin();it!=s.end();it++){ num[*it]=cnt;cnt++; } parent.assign(s.size()+1,-1); for(int i=0;i

정답1. n= 10000000 까지인데 n개짜리 배열 만들었다가 메모리 초과.. n/2+1 까지 확인하는것으로 변경하고 예외적으로 1,2는 n/2+1가 자기 자신까지 될수 있어서 2보다 큰 숫자들만 자기 자신일 경우 +1 해주었다. #include #include using namespace std; int main() { int n; cin>>n; int cnt=0; vectorarr(n/2+2,0); for(int i=1;i

시간초과 #include #include #include using namespace std; int main() { int n,s; //길이가 가장 짧으면서 s이상인거 cin>>n>>s; vectorarr; arr.assign(n+1,0); for(int i=1;i>arr[i]; arr[i]+=arr[i-1]; } //1...n개짜리 길이 for(int i=1;i=s){ cout

투포인터 문제 #include #include #include using namespace std; int main() { int n,x; cin>>n; vectorarr; int t; for(int i=0;i>t; arr.push_back(t); } cin>>x; sort(arr.begin(),arr.end()); int cnt=0; int left=0; int right=n-1; if(n==1 && arr[0]!=x){ cout

서로 다른 3글자라서 조합을 nCm 해야하나? 했는데 결국 순서가 정해질테고 그냥 제일 상위몇개만 하면되었다.. 어렵다 #include #include #include #include using namespace std; //숫자 배열을 문자열로 string turn(vectorarr){ string tmp=""; for(int i=0;i>n; vectorarr(n); for(int i=0;i>arr[i]; } //조합을 해야하지 않을까? 했는데 그냥 상관업나 vectormins(n+1); vectormaxs(n+1); for(int i=0;i

next_permutation은 {1,2,3,4} 가 주어지면 1,2,4,3 과 같이 다음에 넘어갈 수열이 있으면 실행 prev_permutation은 {1,2,4,3}이면 {1,2,3,4} 과 같은게 있으면 실행한다. #include #include #include using namespace std; vectorarr; int cal(vectorvisited){ visited.push_back(visited[0]); //중간에 길 끊기면 경로 아님 int cnt=0; for(int i=0;i>n; vectorvisited; arr.assign(n,vector(n,0)); visited.assign(n,0); for(int i=0;iarr[i][j]; } visited[i]=i; } //1->2->3-..