슬라이딩 윈도우(Sliding Window)란?
슬라이딩 윈도우는 배열, 리스트 또는 문자열과 같은 연속된 데이터 구조에서 부분집합을 효율적으로 탐색하거나 계산하기 위해 사용되는 알고리즘 기법이다.
특히, 고정 길이 또는 가변 길이의 부분 집합에 대해 반복적으로 계산할 때 유용하다.
1. 기본 원리
슬라이딩 윈도우는 데이터를 처음부터 끝가지 순회하면서, 고정된 크기 또는 조건에 따라 움직이는 윈도우를 유지한다.
- 윈도우(Window): 현재 부분 집합을 나타내는 데이터의 범위(시작점과 끝점으로 표현).
- 슬라이딩: 윈도우를 한 요소씩 오른쪽으로 이동시켜 새 값을 포함하거나 오래된 값을 제외.
2. 작동 원리
-
초기화
- 시작점과 끝점을 설정한다.
- 필요한 경우 결과를 저장하거나 현재 상태(합, 최대값)를 기록할 변수를 초기화 한다.
-
윈도우 확장
- 끝점을 이동시켜 윈도우를 확장하고 새로운 데이터를 포함한다.
-
조건 검증
- 현재 윈도우가 문제의 조건(크기, 값의 범위 등)을 만족하는지 확인한다.
-
윈도우 축소
- 조건을 만족하지 않는 경우 시작점을 이동시켜 윈도우를 축소한다.
-
반복
- 데이터의 끝까지 도달할 때까지 윈도우를 슬라이드하면서 위의 과정을 반복한다.
3. 주요 예제
슬라이딩 윈도우는 다음과 같은 형태의 문제에 주로 사용된다.
- 고정 크기의 부분 합/평군 구하기
- 문제: 크기가 k인 모든 부분 배열의 합을 구하기.
- 방법:
- 처음에 크기가 k인 부분 합을 계산한다.
- 이후 한 칸씩 오른쪽으로 이동하면서 새로운 값을 더하고 오래된 값을 빼서 계산한다.
- 최대/최소값 찾기
- 문제: 크기가 k인 모든 부분 배열에서 최대값을 구하기.
- 방법:
- 덱(deque)을 활용해 윈도우 내 최대값을 유지한다.
- 특정 조건을 만족하는 부분 배열 찾기
- 문제: 합이
target인 부분 배열의 시작과 끝 찾기. - 방법:
- 윈도우를 확장하면서 합을 계산한다.
- 조건을 초과하면 윈도우를 축소한다.
- 문자열 관련 문제
- 문제: 고유 문자의 개수가 k 이하인 가장 긴 부분 문자열 찾기.
- 방법:
- 해시맵(딕셔너리)로 윈도우 내 문자의 빈도를 기록하면서 조건에 따라 축소/확장한다.
코드
1. 고정 크기 윈도우: 최대 부분 합 구하기
크기가 k인 모든 부분 배열의 합 중 최대값을 구하라.
public class SlidingWindowFixed {
public static int maxSum(int[] nums, int k) {
int n = nums.length;
int currentSum = 0;
// 초기 윈도우 설정
for (int i = 0; i < k; i++) {
currentSum += nums[i];
}
int maxSum = currentSum;
// 윈도우를 슬라이드
for (int i = k; i < n; i++) {
currentSum += nums[i] - nums[i - k]; // 새 값을 추가하고 오래된 값을 제거
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {1, 3, 2, 5, 1, 1, 2, 3};
int k = 3;
System.out.println("최대 부분 합: " + maxSum(nums, k)); // 출력: 10
}
}2. 가변 크기 윈도우: 조건을 만족하는 최대 길이
부분 배열의 합이 target 이하인 경우의 최대 길이를 구하라.
public class SlidingWindowVariable {
public static int maxLength(int[] nums, int target) {
int start = 0; // 윈도우의 시작점
int currentSum = 0;
int maxLength = 0;
for (int end = 0; end < nums.length; end++) {
currentSum += nums[end]; // 새 값을 윈도우에 추가
// 조건을 만족하지 않으면 윈도우를 축소
while (currentSum > target) {
currentSum -= nums[start];
start++;
}
// 최대 길이 갱신
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int target = 7;
System.out.println("최대 길이: " + maxLength(nums, target)); // 출력: 2
}
}3. 문자열: 고유 문자의 개수가 k 이하인 가장 긴 부분 문자열
고유 문자의 개수가 k 이하인 가장 긴 부분 문자열을 찾아라.
import java.util.HashMap;
public class SlidingWindowString {
public static int longestSubstring(String s, int k) {
int start = 0;
int maxLength = 0;
HashMap<Character, Integer> charCount = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
char endChar = s.charAt(end);
charCount.put(endChar, charCount.getOrDefault(endChar, 0) + 1);
// 조건을 만족하지 않으면 윈도우 축소
while (charCount.size() > k) {
char startChar = s.charAt(start);
charCount.put(startChar, charCount.get(startChar) - 1);
if (charCount.get(startChar) == 0) {
charCount.remove(startChar);
}
start++;
}
// 최대 길이 갱신
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
public static void main(String[] args) {
String s = "abcba";
int k = 2;
System.out.println("가장 긴 부분 문자열 길이: " + longestSubstring(s, k)); // 출력: 3 ("bcb")
}
}
Enjoy Develog!