분류 전체보기

백준 2110 공유기설치 c++ // 매개변수탐색, 이분탐색 hard

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 의사코드 1. 첫번째 집을 선택하는게 최선인가? ㅇㅇ 귀류법 : 첫번째집을 선택안하는게 최선이라고 가정 -> ex) 1 2 5 에서 2부터 2개선택(2,5) 하는경우 간격은 3 / (1,5)선택하는 경우 간격이4 -> 모순 - > 따라서 첫번쨰 집을 선택하는게 최적해를 보장한다. 2. 가장 중요한점은 st, en이 v의 값이 아닌 집간 최소..

프로그래머스 귤고르기 c++ // 공간복잡도 공식, 구현

https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 공간복잡도 공식 512MB == int배열[1억] 임을 기억하자. 2. 의사코드 1. arr을 정렬함 //a[i] : i의 등장횟수 ex) arr : 2 2 2 1 1 k=6, O O O 2. k와 arr[i]를 -하면서 k가 0이될때까지 뺴면됨. 3. arr[i]가 0이될때마다 ret++ 4. k가 0이되면 종료 and 마지막 0이된숫자를 세주기위해 ret+1 3. 전체코드 #includ..

프로그래머스 달리기경주 c++ // 해쉬맵 기본정렬됨(키값기준오름차순), 구현

https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 0. 해쉬맵은 키값기준 오름차순으로 기본정렬되어 있다. 내림차순하려면 선언시 greater 을 추가하면된다. 1. 의사코드 m1 : 이름, 인덱스 저장 m2 : 인덱스, 이름저장 1. calling(현재이름)으로 이전이름을 찾는다. 2. m1, m2를 각각 값에 알맞게 swap 해준다. ex : m1[kai]=3 , m1[pve]=2 ---> m1[kai]=2, m1[pve]=3 m2[3]=ka..

백준 1253 좋다 c++ // 이분탐색 발상, 주의점(자기자신예외처리)

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 의사코드 1 2 3 3 3 4 i j LB UB 에서 1. 해당수(a[i]+a[j])가 존재한다면, UB-LB로 그 갯수만큼 더해준다 2. 문제 : 1 2 3 3 3 1 2 인 경우 : 3은 앞의 (1,2) 에서도 좋은수에 카운트되고, 뒤의(1,2)에서도 카운트 된다 -> 해결 : vis[LB]를 만들고, 이미 좋은수로 체크된경우 pass 하도록 했다. 3. 문제 : 이분탐색 주의점 : idx 가 i, j와 같은경우 예..

백준 14921 용액합성하기 c++ // 이분탐색 정석패턴

https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 1.의사코드 1. v[i]를 돌면서 -v[i]의 idx를찾는다 2. 정답후보는 idx-1, idx, idx+1이다. 3. 범위쳌 / 자기자신제외 / 정답갱신 2. 전체코드 #include using namespace std; typedef long long ll; ll ret=200000000+1; int n; vector v; int main() { ios::sync..

백준 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. 자기자신제외 ..