슬라이딩 윈도우(Sliding Window)
슬라이딩 윈도우는 알고리즘 기법 중 하나로, 연속된 구간(subarray)을 탐색하거나 비교할 때,
모든 경우를 일일이 보지 않고 '창문(Window)' 처럼 일정한 범위를 이동시키며 탐색하는 방식이다.
슬라이딩 윈도우는 배열이나 리스트처럼 연속적인 데이터에서 부분 구간을 효율적으로 탐색할 때 자주 사용된다.
슬라이딩 윈도우의 특징
-
투 포인터 (Two Pointer) 기반
- 구간의 시작점(left)과 끝(right)을 조절하며 탐색한다.
- 하나의 포인터는 고정하고 다른 하나를 이동시키거나, 둘 다 조금씩 이동한다.
-
효율적인 시간 복잡도
- 단순하게 모든 부분 배열을 탐색하면 O(N²) 이지만,
슬라이딩 윈도우는 대부분의 경우 O(N) 으로 해결 가능하다.
- 단순하게 모든 부분 배열을 탐색하면 O(N²) 이지만,
예시 문제
길이가 N인 배열에서, 연속된 길이 K의 구간 중에서 최댓값을 구하라
- ❌ 브루트포스 방식 - O(N * K)
for (int i = 0; i <= N - K; i++) {
int sum = 0;
for (int j = i; j < i + K; j++) {
sum += arr[j];
}
max = Math.max(max, sum);
}- ✅ 슬라이딩 윈도우 - O(N)
int sum = 0;
// 첫 구간 초기화
for (int i = 0; i < K; i++) sum += arr[i];
int max = sum;
// 윈도우를 오른쪽으로 한 칸씩 이동
for (int i = K; i < N; i++) {
sum = sum - arr[i - K] + arr[i]; // 왼쪽 하나 빼고, 오른쪽 하나 추가
max = Math.max(max, sum);
}슬라이딩 윈도우가 자주 사용되는 유형
-
부분 합 / 평균
- 연속된 K개 수의 최대/최소/평균
-
문자열 탐색
- 패턴 매칭 등
-
최소/최대 길이 또는 구간
- 특정 조건을 만족하는 최소 구간
-
중복 없는 구간 찾기
- 투포인터로 문자열 중복 없는 부분 탐색
예시 문제로, 백준 2461 문제가 있다.
문제 (백준 2461)
KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.
이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43], 2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최댓값과 최솟값의 차이가 17-15=2로 최소가 된다.
대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.
입력
입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 0이상 109이하이다.
출력
대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.
접근 방법
처음에 생각했던 방법은 2가지였다.
✅ 방법 1
- 모두 하나의 배열 또는 List(컬렉션)에 넣고, 정렬한다.
- 이때, 클래스 또는 2차원 배열을 통해 해당 학생의 능력치와, 해당 학생이 어느 학급인지 저장한다.
- 가까운 것부터 탐색하면서 해당 값들이 각각 다른 학급이면 최소값 갱신한다.
❌ 방법 2
- 첫번째 학급을 기준점으로 잡고, 첫번째 학급에서 어떤 학생을 뽑느냐에 따라 최소값을 탐색한다.
- 예를 들어, 첫번째 배열에서 0번째 요소(제일 작은 값)를 뽑는 경우, 나머지 배열을 순회하며 각 요소(능력치)들의 차이가 최소가 될수있는 경우를 이분탐색을 통해 찾는다.
- 첫번째 학급을 반복문을 통해 순회하며 탐색
하지만 방법 2는 1번보다 훨씬 복잡하고 시간도 더 오래 걸렸기 때문에 1번을 선택했다.
방법 1에서 추가로 다음과 같이 접근한다.
- 투 포인터와 슬라이딩 윈도우 기법을 통해 탐색한다.
- 각 학생들을 능력치 기준 오름차순 정렬하기 위해
compareTo()메서드를 재정의한다. count[]배열을 통해 각 학급의 학생이 몇번 나왔는지 알아내고, 첫번째라면total++를 통해 지금까지 나온 학급의 수를 증가시킨다.- total이 N(전체 학급수)에 도달하면 최소값을 초기화시키고, left 포인터를 이동시킨다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class boj_2461 {
static int N, M;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
List<Student> students = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
int skill = Integer.parseInt(st.nextToken());
students.add(new Student(skill, i));
}
}
Collections.sort(students);
int[] count = new int[N];
int total = 0;
int left = 0;
for (int right = 0; right < students.size(); right++) {
int group = students.get(right).group;
if (count[group]++ == 0) total++;
while (total == N) {
int diff = students.get(right).skill - students.get(left).skill;
answer = Math.min(answer, diff);
// left 포인터 이동
int leftGroup = students.get(left).group;
if (--count[leftGroup] == 0) total--;
left++;
}
}
System.out.println(answer);
}
static class Student implements Comparable<Student> {
int skill, group;
public Student(int skill, int group) {
this.skill = skill;
this.group = group;
}
@Override
public int compareTo(Student o) {
return this.skill - o.skill;
}
}
}
