Algorithm/투포인터

프로그래머스 보석쇼핑 c++ //투포인터 ,슬라이딩윈도우, map,set

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 투포인터 ,슬라이딩윈도우 코드형식s,e=0부터시작해서이렇게 움직이는 투포인터를 슬라이딩 윈도우라고 한다.while(1): e가끝 and 조건불만족 -> 탈출! if(조건만족) e가 범위밖이면 continue! +1하기전 자료구조 갱신! e+1 else +1하기전 자료구조 갱신! s+1해당 형식을 암기하자. 2. map,set 활용법set는 se..

백준 22988 재활용캠페인 c++ // 투포인터, /2주의사항, 투포예외처리

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 1. 의사코드 1. n이 10만 -> 완탐불가 -> 투포? 2. s와 e를 움직이며 관찰한다. 3. e가 이미 x이상인경우-> 가능성없음 -> 제거, cnt+1 4. 병을만들수있으면 만든다. (코드참조) 5. 병을못만드는 경우 -> s+1 -> 더큰값과 합치면 병을 만들수 있는지 탐색한다. 5.1. 위에서 ..

백준 16472 고냥이 c++ // 투포인터, 매개변수탐색, 투포의 핵심아이디어, set 존재여부 조사하는법

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 1. 시행착오 1. cnt에 e-1과 e를 비교하여 다르면 cnt를 1증가시킨다. 반례 : cac의 경우 실제 cnt는 2가 되어야하는데, 단순히 e와 e-1을 비교하면 ac에서 a!=c이므로 cnt가 증가되어 버린다.. 2. 해결 : set에 현재 등장한 알파벳들을 저장한다 2. 의사코드 1.while(str의 범위내인지 체크) 2. 현재 알파벳갯수가 n이하인경우 -> 너 가능성있어 -> e를 뒤로보내며..

백준 2470 두용액 c++ // 투포인터는 st,en중 누구를 움직일지 결정하라

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 의사코드 1.1 st,en중 누구를 움직일지 결정하라 if (sum1 커져야함->음수를 줄임 -> st++ else e--; //합이양수 -> 작아져야함 -> 양수를 줄임 -> e++ 1.2 변수 테이블을 정의하라 //ret : 현재까지 값중 0에 가장가까운 합 2. 전체코드 #include using namespace st..

백준 20922 겹치는건 싫어 c++// 투포인터 정석풀이 형식

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 1. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n>>k; for (int i = 0; i < n; ++i) { ci..

백준 22862 c++ // 투포인터 응용방법(db 이용)

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 1. 의사코드 holsu변수를 db로 사용한다. holsu변수 => s~e까지 구간중 홀수의 갯수를 저장, 갱신한다. 2. 전체코드 #include using namespace std; typedef long long ll; ll n, k,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); ..

백준 13144 List Of Unique Numbers c++ // 투포인터, 배열활용

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 1. 배열활용 아이디어 vis[해당숫자] 방문여부표시 => 중복숫자인지 검사 2.전체코드 #include using namespace std; typedef long long ll; ll n, m,ret,temp; vector v; int vis[1000000 + 1];//해당숫자 방문했는지 여부 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; ..

백준 2003 수들의합2 c++ // 투포인터 정석풀이

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 주의사항 v.push_back(0); 마지막에 0을넣어야 e++되면서 0을 가르킴 => out of index 방지 2. 전체코드 #include using namespace std; typedef long long ll; ll n, m,ret,temp; vector v; int main() { ios::sync_with_stdio(0); cin.ti..