명이나물 라이브러리View
슬라이딩 윈도우
코딩테스트를 준비하면서 이번에는 슬라이딩 윈도우 알고리즘을 공부했다.
이름만 들었을 때는 조금 낯설었는데, 개념을 하나씩 정리해보니 생각보다 직관적인 방식이었다.
말 그대로 창문을 옆으로 밀듯이, 일정한 구간을 유지하거나 조절하면서 배열이나 문자열을 탐색하는 방법이다.
처음에는 투 포인터와 비슷해 보여서 헷갈렸다.
특히 left, right를 같이 쓰는 문제들이 많다 보니, 이게 투 포인터인지 슬라이딩 윈도우인지 구분이 잘 안 됐다.
공부하면서 내가 이해한 기준은 이렇다.
고정 길이 구간 문제는 슬라이딩 윈도우로 접근하기 좋다.
가변 길이 구간 문제는 left, right 포인터를 조절하는 투 포인터 방식으로 접근한다.
다만 가변 길이 문제도 현재 구간의 상태를 유지하면서 이동하기 때문에,
넓은 의미에서는 슬라이딩 윈도우로 볼 수 있다.조금 더 쉽게 말하면,
고정 길이 = 윈도우 크기가 정해진 슬라이딩 윈도우
가변 길이 = 조건에 따라 윈도우 크기를 조절하는 투 포인터 방식이라고 이해했다.
슬라이딩 윈도우를 사용하는 이유
배열에서 연속된 구간의 합을 구해야 한다고 생각해보자.
예를 들어 아래 배열에서 길이가 3인 구간의 합을 구한다고 하면,
[1, 2, 3, 4, 5]단순하게는 이렇게 계산할 수 있다.
1 + 2 + 3
2 + 3 + 4
3 + 4 + 5물론 이렇게 해도 답은 구할 수 있다.
하지만 배열의 길이가 커지고, 구간의 길이도 길어진다면 매번 구간 전체를 다시 계산하는 방식은 비효율적이다.
여기서 슬라이딩 윈도우를 사용하면 계산을 줄일 수 있다.
처음 구간의 합을 구한 뒤,
1 + 2 + 3 = 6다음 구간으로 이동할 때는 전체를 다시 더하지 않고,
6 - 1 + 4 = 9처럼 처리한다.
기존 구간에서 빠지는 값은 빼고, 새로 들어오는 값은 더하는 방식이다.
즉, 슬라이딩 윈도우의 핵심은 이것이다.
매번 구간 전체를 다시 계산하지 않고,
변경되는 값만 갱신한다.이렇게 하면 불필요한 반복을 줄일 수 있다.
내가 이해한 슬라이딩 윈도우의 핵심
슬라이딩 윈도우는 결국 연속된 구간을 효율적으로 관리하는 방법이다.
구간이 이동할 때 실제로 바뀌는 값은 많지 않다.
이전 구간: [1, 2, 3]
다음 구간: [2, 3, 4]이 경우 2, 3은 그대로 남아 있고, 1이 빠지고 4가 들어온다.
그래서 매번 [2, 3, 4]를 새로 계산하는 것이 아니라,
기존 구간에서 1을 제거
새로운 구간에 4를 추가이렇게 현재 구간의 상태만 갱신한다.
공부하면서 느낀 점은, 슬라이딩 윈도우 문제에서는 단순히 반복문을 돌리는 것보다 현재 구간에서 무엇을 유지할 것인지를 먼저 생각하는 것이 중요하다는 것이다.
예를 들면 다음과 같다.
구간의 합을 유지할 것인지
구간 안의 개수를 유지할 것인지
구간 안의 최댓값이나 최솟값을 유지할 것인지무엇을 유지해야 하는지에 따라 사용하는 변수나 자료구조가 달라진다.
고정 길이 슬라이딩 윈도우
가장 먼저 이해한 유형은 고정 길이 슬라이딩 윈도우이다.
구간의 크기가 정해져 있는 경우에 사용한다.
예를 들어 이런 문제다.
길이가 K인 연속 구간의 합 중 최댓값을 구하라.이 경우 윈도우 크기는 항상 K로 고정된다.
[1, 2, 3, 4, 5], K = 3
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]고정 길이 문제는 흐름이 비교적 단순하다.
1. 처음 K개의 값을 이용해 첫 구간을 만든다.
2. 첫 구간을 정답 후보로 확인한다.
3. 오른쪽으로 한 칸 이동한다.
4. 왼쪽에서 빠지는 값을 제거한다.
5. 오른쪽에서 들어오는 값을 추가한다.
6. 현재 구간으로 정답을 갱신한다.Java로 표현하면 대략 이런 형태가 된다.
int sum = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
int max = sum;
for (int right = k; right < arr.length; right++) {
int left = right - k;
sum -= arr[left];
sum += arr[right];
max = Math.max(max, sum);
}여기서 처음에 헷갈렸던 부분은 이 코드였다.
int left = right - k;왜 right - k가 빠지는 위치인지 바로 와닿지 않았다.
예를 들어 k = 3이고, 처음 구간이 0, 1, 2라고 하면 다음에 새로 들어오는 위치는 3이다.
이전 구간: 0, 1, 2
다음 구간: 1, 2, 3이때 빠지는 위치는 0이다.
left = right - k
left = 3 - 3 = 0그래서 오른쪽에서 새 값이 들어올 때, 빠지는 왼쪽 값의 위치를 right - k로 구할 수 있다.
고정 길이 문제는 이런 식으로 윈도우 크기를 유지한 채 한 칸씩 이동하면 된다.
가변 길이 슬라이딩 윈도우와 투 포인터
슬라이딩 윈도우가 항상 고정 길이로만 사용되는 것은 아니다.
조건에 따라 구간의 길이가 늘어나거나 줄어드는 경우도 있다.
이런 유형은 보통 투 포인터 방식으로 접근한다.
예를 들어 이런 문제다.
합이 S 이상이 되는 가장 짧은 연속 구간의 길이를 구하라.이 경우 구간 길이는 고정되어 있지 않다.
보통 오른쪽 포인터를 이동하면서 구간을 늘리고, 조건을 만족하면 왼쪽 포인터를 이동하면서 구간을 줄인다.
int left = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= arr[left];
left++;
}
}이 코드는 right를 이동하면서 구간을 확장하고,sum >= target 조건을 만족하면 left를 이동하면서 구간을 줄인다.
처음에는 이게 투 포인터인지 슬라이딩 윈도우인지 헷갈렸다.
정리해보면 이렇게 이해하면 될 것 같다.
고정 길이 구간 문제
→ 윈도우 크기가 정해져 있으므로 슬라이딩 윈도우 느낌이 강하다.
가변 길이 구간 문제
→ left, right를 조건에 따라 조절하므로 투 포인터 느낌이 강하다.
하지만 가변 길이 문제도 현재 구간의 합, 개수, 상태를 유지하면서 이동하기 때문에
넓은 의미에서는 슬라이딩 윈도우로 볼 수 있다.즉, 둘을 완전히 다른 개념으로 나누기보다는,
연속된 구간을 효율적으로 탐색하는 방법이라는 큰 틀에서 이해하는 게 더 편했다.
고정 길이와 가변 길이 비교
공부한 내용을 정리하면 다음과 같다.
| 구분 | 설명 | 대표 예시 |
|---|---|---|
| 고정 길이 슬라이딩 윈도우 | 구간 크기가 정해져 있음 | 길이 K 구간합, 10일 할인 행사 |
| 가변 길이 슬라이딩 윈도우 | 조건에 따라 구간 크기가 변함 | 합이 S 이상인 최소 구간 |
| 투 포인터 | left, right를 조절하며 조건 탐색 | 가변 길이 구간 문제에서 자주 사용 |
내가 이해한 한 줄 정리는 이렇다.
고정 길이는 슬라이딩 윈도우 대표 유형,
가변 길이는 투 포인터를 활용한 슬라이딩 윈도우 유형이다.구간 안의 개수를 관리해야 하는 경우
슬라이딩 윈도우 문제 중에는 단순히 합만 관리하면 안 되는 문제도 있다.
예를 들어 현재 구간 안에 특정 값이 몇 개 있는지 알아야 하는 경우다.
이럴 때는 보통 HashMap이나 배열을 사용해서 개수를 관리한다.
Map<String, Integer> map = new HashMap<>();값이 새로 들어오면 개수를 증가시킨다.
map.put(item, map.getOrDefault(item, 0) + 1);여기서 getOrDefault()는 해당 key가 없으면 기본값을 반환한다.
처음 등장하는 값이라면 기존 개수가 없기 때문에 0으로 보고, 거기에 1을 더하는 방식이다.
반대로 값이 빠질 때는 개수를 감소시킨다.
map.put(item, map.get(item) - 1);그리고 개수가 0이 되면 제거하는 것이 좋다.
if (map.get(item) == 0) {
map.remove(item);
}처음에는 개수가 0이면 그냥 둬도 되지 않나 싶었다.
하지만 Map끼리 비교하는 문제에서는 0인 key가 남아 있으면 다른 Map으로 판단될 수 있다.
예를 들어 아래 두 Map은 사람 눈에는 비슷해 보여도 Java에서는 다르다.
A = {apple=1, banana=1}
B = {apple=1, banana=1, rice=0}rice가 0개라도 key가 존재하기 때문에 A.equals(B)는 false가 된다.
그래서 Map으로 현재 구간의 상태를 관리할 때는, 개수가 0이 된 값은 제거하는 습관을 들이는 게 좋겠다고 생각했다.
슬라이딩 윈도우 문제를 알아보는 기준
공부하면서 정리한 기준은 이렇다.
문제에서 아래와 같은 표현이 나오면 슬라이딩 윈도우를 의심해볼 수 있다.
연속된 부분 배열
연속된 문자열
K개 구간
며칠 동안
부분합
가장 긴 구간
가장 짧은 구간
구간 안의 개수특히 중요한 키워드는 연속된 구간이다.
연속되지 않은 값을 고르는 문제가 아니라, 배열이나 문자열에서 이어진 범위를 다룬다면 슬라이딩 윈도우를 떠올려볼 만하다.
문제를 풀 때 생각할 순서
앞으로 슬라이딩 윈도우 문제를 만나면 바로 코드를 작성하기보다, 먼저 아래 순서로 생각해보려고 한다.
1. 연속된 구간을 다루는 문제인가?
2. 구간 길이가 고정되어 있는가, 변하는가?
3. 현재 구간에서 유지해야 할 값은 무엇인가?
4. 구간이 이동할 때 빠지는 값은 무엇인가?
5. 새로 들어오는 값은 무엇인가?
6. 첫 번째 구간도 따로 확인해야 하는가?특히 고정 길이 윈도우에서는 첫 번째 구간을 만든 뒤 바로 정답 후보로 확인해야 한다.
반복문을 오른쪽 인덱스 기준으로 돌리다 보면, 첫 구간을 놓칠 수 있기 때문이다.
자주 실수할 것 같은 부분
첫 번째 구간을 확인하지 않는 실수
고정 길이 윈도우에서는 처음 구간도 정답 후보이다.
따라서 처음 구간을 만든 뒤 바로 확인해야 한다.
int max = sum;또는 Map 비교 문제라면 이런 식으로 확인해야 한다.
if (targetMap.equals(windowMap)) {
answer++;
}빠지는 인덱스를 헷갈리는 실수
고정 길이 윈도우에서 오른쪽 값이 새로 들어올 때, 빠지는 인덱스는 보통 이렇게 구한다.
int left = right - k;처음에는 헷갈릴 수 있지만, k만큼 떨어진 왼쪽 값이 빠진다고 생각하면 이해하기 쉽다.
Map에서 0개가 된 key를 남겨두는 실수
Map으로 개수를 관리할 때는 개수가 0이 된 key를 제거해야 한다.
if (map.get(item) == 0) {
map.remove(item);
}특히 equals()로 Map을 비교하는 문제에서는 이 부분이 중요하다.
get()과 getOrDefault()를 헷갈리는 실수
Java에서 Map.get()은 기본값을 받을 수 없다.
map.get(item, 0); // 잘못된 사용기본값이 필요하면 getOrDefault()를 사용해야 한다.
map.getOrDefault(item, 0);정리
슬라이딩 윈도우는 연속된 구간을 효율적으로 탐색하기 위한 알고리즘이다.
처음에는 단순히 “구간을 옆으로 민다” 정도로만 이해했는데, 공부하면서 핵심은 현재 구간의 상태를 유지하는 것이라는 생각이 들었다.
매번 구간 전체를 새로 계산하는 것이 아니라,
빠지는 값 제거
들어오는 값 추가
현재 구간 상태로 정답 갱신이 흐름을 반복한다.
그리고 고정 길이와 가변 길이에 대해서는 이렇게 정리할 수 있을 것 같다.
고정 길이는 윈도우 크기가 정해진 슬라이딩 윈도우,
가변 길이는 조건에 따라 윈도우 크기를 조절하는 투 포인터 방식의 슬라이딩 윈도우.슬라이딩 윈도우 문제를 풀 때는 구간을 어떻게 이동시킬지보다 먼저, 현재 구간에서 어떤 정보를 관리해야 하는지를 생각하는 게 중요할 것 같다.
구간합 문제라면 합을 관리하고, 개수 비교 문제라면 Map을 관리하고, 최댓값이나 최솟값이 필요하다면 다른 자료구조까지 고려해야 한다.
아직 익숙한 알고리즘은 아니지만, 배열이나 문자열에서 연속된 구간이 나오면 앞으로는 슬라이딩 윈도우를 먼저 떠올려보려고 한다.
'CS > 알고리즘' 카테고리의 다른 글
| 투포인터, 두 개의 포인터로 탐색을 줄이기 (0) | 2026.05.23 |
|---|