Algorithm/슬라이딩 윈도우

[알고리즘] 백준 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..