Algorithm4 0-1 knapsack problem with Brute force. Programming rule. 1. benefit vale & weight 는 Random number generator function 을 통해 만든다. (benefit value 는 1~500, weight 는 1~100) 2. Maximum capacity W = items number * 25. 먼저, #include #include srand(time(NULL)); // seed the random number generator 난수를 만들고 int max_items; int n; int *val = new int[n]; int *wt = new int[n]; int W; 우리는 items개수가 11개, 21개, 31개일떄를 볼것이기때문에 for (n = 11; n 2023. 5. 5. 수열 2559 c++ queue,vector,sort 시간초과에 걸렸던 문제였다. 처음 접근 vector a에 다 받아놓고 vector sum에 합을 넣어놓는다. -> 이중 for문을 써서 for(int i = 0; i < n - k; i ++){ arrsum = 0; for(int j = i; j < i + k; j++){ arrsum += a[i]; } sum.push_back(arrsum); } 이러고 밑에서 sort(sum.rbegin(), sum.rend()); 하고 sum[0] 을 출력하면 된다 그런데 시간초과!!!! 이유는? 이중배열.. 그럼 이중배열을 안쓰며 한큐에 해결할수 있는건? 바로바로 큐 를 이용하는것이다. 큐의 크기가 k 가 되기전까진 넣기만 하고 k일때부터 그들의 합을(합은 애초에 넣을때부터 누적해야한다 arrsum) vec.. 2023. 1. 8. 백준 단어정렬 1181 c++ 단순정렬? -> 글자수가 같으면 사전순서대로 그안에서 정렬/ 단어가같으면 한개만 출력. 여기서 아이디어는 동적배열로 일단 단어들 다 저장하자. 글자수가 1개인거부터 50개인거까지 순서대로 점검하며 각 글자수마다 여러개가있으면 vector에 넣고 정렬돌리자. 정렬했는데 만약 같은 단어가 둘다 존재한다면? 안된다. 애초에 벡터에 넣을때 같은단어가 있는지 체크하고 이미 push_back된 단어와 겹치면 (2) 에서는 push_back을 하지 않아야 한다. 끝. ------------------------------------------------------------------------------------------------------------------------------- 1번을 보면 이렇.. 2022. 10. 18. 백준 11399 ATM c++ 이번 문제의 해결방법은 먼저 돈을 뽑는사람이 총합에 더 큰 기여를 하기 때문에 최솟값을 만들려면 돈뽑는데 시간이 조금걸리는 사람이 먼저 뽑는것이다. 그렇다면 각 사람이 걸리는 시간의 input을 정렬해서 사용하면 될 것이다. 정렬을 고려하며 배열을 사용하고자한다 (n이 정해지지않았기에 동적배열) sort(arr,arr+n); #include STL을 사용하여 정렬오름차순을 한다. 앞의 사람이 걸린시간은 총 n번 반복되고 마지막사람은 1번반복된다. 이런식으로 반복횟수를 정해주고 총합시간을 갱신해주면 된다. 끝 2022. 10. 13. 이전 1 다음
