Mini

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 1. 우선순위큐 정렬방법 매개변수가 같으면 false를 리턴해야함에 주의하자. class cmp { public: bool operator () (pair p1, pair p2) { if (p1.first == p2.first) { return p1.second p2.first; } }; 2. 문제점 기한순 정렬후 최대컵라면 뽑는방법 -> 기한을 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1.시간복잡도 정렬후 mid 인덱스 출력 - > N ( 10만) * NlgN(정렬) -> 시초 특정알고리즘 필요 : pq, dp, 이분탐색 등.. 정렬한효과 -> pq 2개로 구현 2. 의사코드 maxHeap의 top이 항상 중간값이 되도록 고정하면 자동정렬이 된다. 이럴려먼 maxHeap의 크기가 minHeap의 크기보다 같거나 1이 커야한다. 1. 입력온값을 어디에 넣을것인가?..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1.의사코드 1. 작은것부터 넣기 2. 메모리제한 -> 큐에n개이상이면 pop 하기 3. top에 있는애가 n번째 큰수임 ex) 1~7에서 5번째 큰수는 3이다. pq에 6이 올때, 5(n) top(1제거) pq에 7이 올때, 5(n) top제거(2제거) 이후 top 에있는 놈이 정답인 3이다. 2. 전체코드 ios sync 코드를 빠뜨렸더니 시간초과가 났다.. #include using namespac..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 의사코드 1. 최소값을 2개씩더하고, q에넣기, 정답에 더하기 하면된다 이방법이 왜 최적인지는 허프만코드 알고리즘과 동일하므로 이를 참고하면 된다. 2. 내코드 #include using namespace std; int ret,n; priority_queue pq; int main() { cin.tie(0); cin >> n; while (n--) { int tmp; cin ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱www.acmicpc.net1.의사코드 2. 전체코드v: 5 6(i+1)a: +(i)#include using namespace std;int N,p,m,g,na,ret1=-1000000000 -1;int ret2 = 1000000000+1;vector v;//n번째자리, 들어갈연산void dfs(int n, vector a,int P,int M,int G,int NA)..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net1.의사코드dfs(n) : n번째사람이 1팀으로가거나 2팀으로 가거나... 이진트리탐색dfs(a, b) : 1팀들의 리스트, 2팀들의 리스트계산부분 : 2중반복문으로 해결v : 0 1 2 ij(i,j) : 0,0/ 0,1 /0,2 /1,0 ... 2. 전체코드#include using namespace std;int N,M,arr[24][24];int ret = 987654321;//n번째사람이 1팀으로감or2팀으로감voi..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 의사코드 def dfs(n, sm): //dfs(인덱스, 현재돈) global ans # [1] 종료조건: 가능한 n을 종료에 관련된것으로 정의! if n>=N: ans = max(ans, sm) return # [2] 하부호출: 화살표 개수만큼 호출 if n+T[n] n) return; //마지막 수업을 들을수 없는경우(막날수업이 2일이상 소요되는경우) dfs(day+v1[day].first, money + v1[day].second); //해당강의선택 dfs(day+1, money); //미선택 } int main() { c..

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1. 의사코드 1. 숫자 -> 크기순 idx로 변환한다 ex : 10 20 30 -> 0 1 2 ex2: 1 2 3-> 0 1 2 2. 변환후 같은배열이면, 같은우주이다. 2. 구현 1. v에 arr복사, 고유값만 남기기 2. v를 이분탐색하며 arr을 arr(idx)로 교체하기 3. 전체코드 #include using namespace std; int m, n,ret,arr[104][10..