목록Algorithm/슬라이딩 윈도우 (5)
Mini
[맞음] 백준 12891 비밀번호 DNA // 슬라이딩 윈도우
https://www.acmicpc.net/problem/12891 * 풀이n = 1백만O(n) 풀이 필요슬라이딩 윈도우==구간(m)을 유지갱신 하면서map에 저장각 구간마다 적은게있는지 검사#includeusing namespace std; typedef long long ll;ll n,m,ret;string str;vector v;map mp;int a,b,c,d;int check() { if(mp['A'] >n>>m>>str; cin>>a>>b>>c>>d; int s=0; int e=0; //안포함 for(int i=0;i
[알고리즘] 백준 11003 최솟값 찾기 // 슬라이딩 윈도우, 덱
https://www.acmicpc.net/problem/11003* 완전탐색N개 숫자에대해 앞의 L 개 탐색 -> O(NL) -> 불가N이 500만이므로, 1번의 탐색만으로 끝내야함! * 행동영역슬라이딩 윈도우에서 덱을 활용하라.나보다 큰값을 pop 반복으로 완탐,정렬 효과를 만들어라. * 풀이삽입하기전, 우측부터 비교 크면 pop 반복 => 완탐효과, 정렬효과, 좌측이 최소값 효과!!작으면 통과push data좌측이 윈도우를 넘어가면 삭제 (인덱스 비교)좌측(최소값) 출력 * 전체코드#include using namespace std;typedef long long ll;ll n, L;ll arr[5000000 + 4];deque> d; // int main() { ios_base::sync_w..
리트코드 3. 반복되는 문자가 없는 가장 긴 부분 문자열 c++ // 슬라이딩 윈도우
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/* 의사코드1. map에 해당문자의 등장횟수기록2. 해당문자가 2회이상등장 -> 등장횟수가1이 될때까지 l을 우측으로 조정3. 모든 중복문자없는 부분문자열을 탐색하면서 그때의 최대값을 ret에 저장함* 전체코드class Solution {public: int lengthOfLongestSubstring(string s) { unordered_map m; //m[a]=2, a의 등장횟수가2임 int r=0,l=0,n=s.size(), ret=0; while(r1){ //2회이상인경우, 1회가되도록 조정해야함..
백준 2096 내려가기 c++ // dp도안되면? 슬라이딩 윈도우
https://www.acmicpc.net/problem/2096 꽤나 애먹었던 문제이다...1. 시간복잡도 분석완탐 -> 3^100000 -> 시간초과dp -> [y][x] -> 3*100000 -> 메모리초과(4MB) -> ?? 2. 슬라이딩 윈도우입력을 모두 받지않고, 입력이 들어오면 그때그때 처리한다.모든입력에대해 아래 그림처럼 ㅁ 칸만 보고 그때그때 처리한다. 3. 의사코드1. 역발상이 필요한데mx배열중 가능한 최대값을 먼저 고른후, cur값과 더해야한다!2. 주의사항그 값을 pqr에 저장후 사용해야함이유 : min[0] = min(mi[0], mi[1]) 이런식으로 진행되는데위에서 min[0]값을 바꿔버리므로, 다음 min[1] 계산할때 오답이나온다. #include using namespa..
[틀림] [자바] 프로그래머스 보석쇼핑 c++ //슬라이딩윈도우, map,set, size를 활용하라.
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..