분류 전체보기

백준 1654 랜선자르기 c++ // 이분탐색, parametric search

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. parametric search 최적화문제 -> 결정문제로 바꿔서 해결한다. 단, 감소또는 증가함수에서만 사용가능하다. 이경우에는 랜선길이up => 랜선갯수down 이다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ N개로만들수있는 랜선의 최대길이 -> 랜선길이가x일때, 랜선갯수가 N개이상인가? 2.의사코드 while (st < en) { ll mid = (st +..

백준 2295 세수의합 c++ // 이분탐색 발상

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. 이진탐색 발상 nC2들의 합배열 : two a를 탐색(n^2) * 이진탐색(lgN) 부분합을 구한후, 이진탐색을 하라!!! 2.의사코드 a[i]+a[j]+a[l]=a[k] 인 k 의 최대값 찾기 two(a[i]+a[j])==a[k]-a[l]인 k의 최대값 찾기! 3. 전체코드 #include using namespace std; typedef ..

백준 18870 좌표압축 c++ // 이분탐색

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 1. 시행착오 답 : 해당원소보다 작은 원소의 갯수 upper_bound - lower_bound 하면 정답이 아니다... lower-begin 이 정답이다. 2. 전체코드 #include using namespace std; int n,m; vector v1,v2; set s; int main() { ios_base::sync_with_stdi..

백준 10816 숫자카드2 c++ // 이분탐색, upper_bound, lower_bound

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 1. upper_bound, lower_bound(begin, end, target) 이분탐색으로 target원소중 가장 우측, 좌측 인덱스 반환 2.전체코드 #include using namespace std; int n,m; vector v; int main() { /* * 이진탐색 -> 2^50 -> 시간초과 * 역발상 : target에서 start로 수렴..

백준 1920 수찾기 c++ // 이분탐색 stl

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 이분탐색 stl binary_search(begin, end , target) 넣으면 target이 있으면1, 없으면0 리턴해줌 2. 전체코드 #include using namespace std; int n,m; vector v; int main() { cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) {..

백준 12919 A와B2 c++ // 완탐, 거꾸로탐색

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 1. 거꾸로탐색 /* * 이진탐색 -> 2^50 -> 시간초과 * 역발상 : target에서 start로 수렴하도록 변경! */ 2. 전체코드 #include using namespace std; string s, t,temp; int ret; //현재k문자열이 만들어짐 void dfs(string k) { //cout 가망없음 if (s.size() >=..

백준 17471 게리멘더링 c++ // 비트마스킹, dfs

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 의사코드 노드번호 : 6 5 4 3 2 1 비트마스킹 : 0 0 0 0 1 1 //값이 1인노드는 1번구역, 값이0인 노드는 0번구역을 뜻함. dfs를 돌았는데, 미방문노드가 있다? -> 불가능 2. 시행착오 - 문제 : 연결만되있으면 모두 방문이 되버리는 문제 dfs에 구역이 다르면 탐색을 끝내도록 로직추가함. 3. 전체코드 #include using namespace std; int n, people[11],..

백준 1285 동전뒤집기 c++ // 비트마스킹 개선방법

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 1. 비트마스킹 개선방법 행탐색(2^20) * 열탐색(2^20) -> 2^40 -> 터진다. 해결 : 행만바꾼후, 열은 최적해가 정해져있다. -> 열을 노가다로 탐색X ex) HTT 가 열인경우, 뒤집으면 THH가 된다. -> 뒤집는게 최적해다! THH가 열인경우, 안뒤집는게 최적해다! 결론 : 행만뒤집은후, t가 절반보다많으면 뒤집으면된다! 2. 전체코드 #include using names..