Hoon222y

문제를 간단하게 정리하자면 친구관계로 묶여 있는 그래프가 있는데 그 그래프에서 모든쌍의 최단거리를 구하는 문제이다그래프끼리의 간선의 가중치는 같다고 본다. 가중치가 다르다면 다익스트라 방식으로 접근해야 할 것이다.플로이드 머셜에 대한 내용은 다음시간에 정리하는것으로 보고 이번시간에는 이 문제를 접근하는 방식에 대해서 먼저 생각해보도록 하자 그래프 내에서 각 간선들의 가중치는 같고 그 그래프 내에서의 모든쌍의 최단경로를 구하는 문제의 경우에는 플로이드 머셜 알고리즘을 사용하는데 알고리즘의 중요부분은 다음과 같다. for(int k=1;k

문제가 길어서 .... 문제를 짧게 설명하자면 책의 번호가 저렇게 정렬되어 있는데 순서대로 정렬을 할 때 최소의 노동력으로 정렬할 때 그때의 최소 노동력을 구하는 것이다.이번 문제의 경우도 해매고, 해매고 ... 이 문제는 LIS알고리즘을 활용 한 것 이라는데 Longest increasing Subsequence 알고리즘으로 이 문제의 포인트는 최소한의 노동력 = 전체값 - 그대로 두는 노동력의 최대값이라고 볼 수 있다는 것이다.대략의 과정을 설명 하자면 앞에서 부터 시작을 한다. 813.8을 마지막으로 하는 정렬된 수열은 당연히 하나이므로 절약할 수 있는 노동력은 6이다.그 다음 812의 경우에는 812보다 작은 수가 없으므로 6 혹은 자기 자신의 노동력 20 중 그대로 두는 노동력이 큰 20이 저장..

그렇다 .. 처음 접근 했을때 ... 못풀었다 ㅋㅋㅋㅋㅋㅋㅋ 처음에 접근 방식을 완전 탐색? 뭐 이렇게 생각을 했었는데 전에 문해기 시간 때 했던 DP와 비슷한 접근이었다. 이 유형의 문제가 DP의 2가지중 하나의 대표적 유형이라고 한다.(힙색이었나? 배낭DP라고 했던듯 ...)일단 내 코드다. #include#include using namespace std; long long arr[100001];long int dp[100001]; int main(){ int num; int weight; memset(dp,0,sizeof(dp)); memset(arr,0,sizeof(arr)); cin >> num >> weight; for(int i=1;i> a >> b; arr[i] =a*1000000LL+b..

예전에도 한번 풀어봤던 문제이다. 방학때 공부하는 책 한권을 완성하기 위해 다시 풀어보는 과정중에 next_permutation을 사용하여 접근을 해보았다. #include//#include #include#include#include using namespace std; int arr[56];int answer;int stuNum;int setNum;bool gett[56];vector v;vector::iterator iter; int check(int a){ for(int i=0;i> testCase; //scanf("%d",&testCase); // next_permutation 쓸꺼임 while(testCase--){ answer =0; memset(gett,true,sizeof(gett)); ..

123456789#include #include using namespace std; int main(){ char a; scanf("%c", &a); printf("%d" ,a);}cs