슬라이딩 윈도우는 배열이나 문자열 같은 연속된 데이터에서 “부분 구간”을 효율적으로 다룰 때 쓰는 기법이에요. 보통 두 개의 포인터(또는 인덱스)를 사용해서 현재 보고 있는 구간의 시작(left)과 끝(right)을 관리하고, 구간을 한 칸씩 옮기면서 필요한 정보를 갱신합니다.
여기서 윈도우(window)는 배열이나 문자열에서 현재 주목하고 있는 구간(부분배열)을 가리키는 말합니다. 마치 기차 창문을 통해 보이는 구간만 보는 것처럼, 배열에서도 우리가 한 번에 살펴볼 ‘크기 K짜리 창문’을 생각하는 거죠.
left = 0, right = 0 (아직 원소를 포함하지 않은 빈 구간)right를 K-1까지 이동시켜 초기 합이나 정보 계산right를 한 칸씩 오른쪽으로 옮길 때마다 새로 들어오는 원소를 구간 정보에 더하고,left 위치)만큼 빼 준 뒤 left++S 이하일 때)만큼 right를 늘렸다가, 조건을 벗어나면 left를 늘려서 다시 조건을 만족시키는 식으로 조절이 과정을 통해 매번 구간을 새로 계산하는 대신 빠져나가는 값·들어오는 값만 업데이트하므로 시간 복잡도를 O(N)으로 줄일 수 있어요.
| 구분 | 설명 |
|---|---|
| 고정 크기 | 윈도우 크기 K가 주어져 있고, 항상 K개의 원소만 고려 (ex. 길이 K 연속 부분배열 합의 최댓값) |
| 가변(투 포인터) | 조건을 만족하는 최대/최소 길이를 찾거나 합이 특정 값이 되는 구간(또는 넘지 않는 구간) 찾기 (ex. 합 ≤ S인 가장 긴 부분배열 길이) |
길이 K인 연속 부분배열 합 최댓값
A와 양의 정수 K가 주어질 때, 길이 K인 연속 부분배열의 합 중 최댓값을 구하세요.A = [3,5,2,6,4], K = 3 → 연속 부분배열 [5,2,6]의 합 13이 최대입니다. NAVER 클라우드·계열사…/**
* @params {number[]} A
* @params {number} K
* @return {number}
*/
solution(A, K){
}
중복 없는 가장 긴 부분 문자열
s가 주어질 때, 중복 문자 없이 만들 수 있는 가장 긴 부분 문자열의 길이를 구하세요.과일 장수 (Fruit Into Baskets)