Algorithm

백준 2473 세용액 c++ // 이진탐색 패턴정석 외우기

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. 의사코드 -97 -6 -2 6 98 103 104 i j LB(idx) 에서 1. 정답후보는 idx-1, idx, idx+1이고, //사실 idx+-2도 탐색을 해야 한다! 2. 조건 : 범위내 && idx가 i또는 j와 달라야되고 && 현재정답보다 최적해여야한다. 2. 내코드 #include using namespace std; typedef long long ll; ..

백준 3151 합이0 c++ // 이분탐색, nC3최적화하는법

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. 의사코드 1. 이진탐색범위 : j+1부터 탐색한다 2. UpperBbound-LowerBbound가 합이3인사람의 숫자이다. //중복없는 ※ 3이 없는경우 ub==lb가 되어 0명이다. 2.전체코드 #include using namespace std; typedef long long ll; ll ret; int n; vector v; set s; int vis[10004]; int main() {..

백준 2467 두용액 c++ //이분탐색 정답후보를 탐색하라

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 0. 시간복잡도 10만*10만 -> 시간초과 -> 10만*이분탐색(log10만) -> 쌉가능 1. 의사코드 -99 -2 -1 4 98 99 100 1. lowerbound로 99를 찾는다. 2. lower_bound 특징(99이상인 위치 리턴) 으로 인해 정답후보는 98 or 99 or 100 중 하나이다. 3. 조건 : 범위내 and 현재정답보다최적 and 자기자신은제외 4. 자기자신제외 ..

백준 1781 컵라면 c++ // 우선순위큐 정렬방법, 선택x인경우 처리방법

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. 문제점 기한순 정렬후 최대컵라면 뽑는방법 -> 기한을 ..

백준 1655 가운데를말해요 c++ // 우선순위큐 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. 입력온값을 어디에 넣을것인가?..

백준 2075 n번째큰수 c++ // 우선순위큐, 발상, 수학

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..

백준 1715 카드정렬하기 c++ // 우선순위큐, 그리디, 허프만코드

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 ..

백준 14888 연산자끼워넣기 c++ // dfs

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1.의사코드 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,in..