728x90
반응형
슬라이딩 윈도우
-
[알고리즘] 투포인터(Two pointers)와 슬라이딩 윈도우(Sliding window)CS기초/Algorithm, Data Structures 2022. 11. 13. 17:51
예제문제는 leetcode로 리뷰할 거기도 하고, 이미 다른데서 포스팅을 많이 해 둬서 특정 문제가 아닌 기본 개념에 집중해서 포스팅을 하려고한다. 투 포인터와 슬라이딩 윈도우의 기본 concept은 다음과 같다. 1. 배열의 특정 두 부분에 포인트를 설정한다. 해당 두 포인터의 사이는 "타겟이 있을 법한 범위"이다. 2. 조건에 따라 해당 포인트를 옮겨가며 타겟을 찾는다. 두 알고리즘의 원리는 같지만 투 포인터의 경우 포인터가 가리키는 값 두 개 자체에만 집중하기 때문에 반복문 loop마다 조건에 따라 포인트 사이의 거리가 달라질 수있지만 슬라이딩 윈도우의 경우 반복문 loop간 window사이의 교집합이 알고리즘의 핵심이기 때문에 두 점사이의 거리가 일정(/고정) 되어있다는 점이 특징이다. 시간 복잡..