분류 전체보기

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

백준 19942 c++ //비트마스킹, 벡터사전순 정렬방법

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1. 벡터사전순 정렬방법 vector 에 넣고 sort 돌리고 vv[0]을 취하면 된다. if (ret == w) { vector vv; vv.push_back(tmp); vv.push_back(arr); sort(vv.begin(), vv.end()); arr = vv[0]; } 2. 전체코드 #include using namespace std; int n, m, mp, mf, ms, mv; ..

프로그래머스 파괴되지않은건물 c++ // dp, 구간합 효율적으로 구하는법

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 구간합 효율적으로 구하는법 1.1 1차원예시 [ 0 , 0 , 0 , 0 , 0] 에 0~3idx까지 a를 더하고싶다 1. [a, 0, 0, 0, -a] 배열 생성 2. ->쪽으로 누적합을구함 3. a배열과 원본배열을 더함. 끝. 1.2 2차원예시 네모친구간에 a를 더하고싶다. 1. 좌측위, 우측아래에 a를 더하고 / 우측위, 좌측아래에 -a를 더한다. 2. ->, 아래쪽으로 누적합을구함 3..