[알고리즘/Algorithm] 슬라이딩 윈도우(Sliding Window) / BOJ 2559 수열

안녕하세요,

이번에는 코딩테스트를 준비하다가 투포인터와 헷갈리는 개념이 있어서 공부해보았습니다.

(투포인터도 조만간 정리해야겠습니다 !)

슬라이딩 윈도우도 정리를 시작 해 보겠습니다 !

---

슬라이딩 윈도우 Sliding Window

---

🔹 개념

 

슬라이딩 윈도우는 배열이나 문자열에서 연속구간을 다룰 때 쓰는 대표적인 테크닉 입니다.

한 번에 전 범위를 훑지 않고, '창(window)-구간'를 왼쪽/오른쪽으로(좌측, 우측 경계만 조금씩 이동) 밀면서 정답을 갱신합니다.

이러한 방식으로 시간복잡도를 크게 줄일 수 있습니다.

 

🔹 핵심 아이디어

1. 연속 구간(subarray / substring)의 값을 다룬다.

- e.g. 합, 길이, 조건 만족 여부 등

2. 창(window), 즉 특정 범위의 구간의 좌측, 우측 경계를 조금씩 한 방향으로만 증가시킨다.

- 되돌아가지 않습니다.

- 창(window) 안의 정보를 해시/배열/데크 등으로 증분 업데이트 시킵니다.

3. 따라서 한 원소가 창(window)에 들어오고(extend), 나가는(shrink)일이 많아야 한 번씩 있습니다.

-> 보통 O(n)

 

즉,

문자열/배열 같은 선형 자료구조에서 왼쪽 포인터 l과 오른쪽 포인터 r로 표현되는 연속구간(창, window)을 유지하면서,  r을 오른쪽으로 밀고 필요하면 l도 오른쪽으로 당겨가며("미는/당기는") 원하는 조건을 만족하는 해를 구하는 기법입니다.

 

매번 새로 계산하지 않고, 이전 계산 결과를 상수 시간으로 갱신하는 것이 핵심입니다!

 

 

🔹 종류

• 고정 길이 윈도우:
  • 길이가 k로 고정되어 있습니다.
  • 양 끝단이 동시에 이동합니다. 즉, 오른쪽으로 한 칸 이동할 때, 왼쪽 값을 빼고 새로운 값을 더합니다. 
• 가변 길이 윈도우:
  • 투포인터라고도 합니다.
  • 조건(합, 종류 수, 빈도 등)에 부합하기 위하여 오른쪽을 확장하며 이동하고, 조건에 벗어날 경우 조건을 유지하기위해 왼쪽을 줄이는 방식으로 양 쪽 끝단을 움직입니다.

🔹 사용시점

• 연속된 구간을 대상으로 합/길이/빈도/개수/최소값/최대값 등을 구할 때 사용합니다.
• 전부 다시 계산하려면 O(NK)가 될 일을, 한 번만 움직여서 선형 복잡도(O(N))로 낮출 수 있을 때 사용합니다.
• ex) 스트리밍, 온라인 처리에 적합합니다.
  • 현재 윈도우 상태만 들고가면 됨
  • 사용하는 공간보 적습니다. (공간복잡도 낮음)
• 고정 길이 윈도우:
  • 길이가 k인 모든 구간의 합/최댓값/평균 등을 구할 때 사용합니다.
  • 예: 길이 k의 최대 부분합
• 가변 길이 윈도우:
  • 조건을 만족하는 가장 긴/짧은 구간을 구할 때 사용합니다.
  • 예: 중복 없는 가장 긴 부분 문자열, 부분합이 S이하인 최장 구간 등
• 데크(Deque)와 결합:
  • 각 윈도우의 최댓값/최솟값을 O(1)로 유지 ("모노톤 데크")할 때 사용합니다.

---

원리와 증명

---

🔹 원리

: 왜 되는가?

: 연속 구간을 한 칸 이동하면 바뀌는 원소는 최대 2 개 입니다. (추가되는 원소 1개, 제거되는 원소 1 개)

-> 합계/빈도/개수/최대값 후보 등을 증분적으로 갱신이 가능합니다.

 

🔹 단조성 / 불변식

가변 윈도우에서는 보통 다음 불변식을 세웁니다.

• 불변식:
  • "현재의 윈도우는 문제의 제약을 만족한다(또는 만족 직전의 상태다)."
• 유지:
  • 오른쪽 포인터를 전진해 만족할 때 까지 윈도우를 확장합니다.
  • 조건을 만족하는 '상태'가 깨질 경우 왼쪽 포인터를 전진시켜 조건을 다시 만족시킵니다.
• 종료:
  • 모든 오른쪽 포인터를 한 번씩 만 전진시키면서 왼쪽도 필요할 때 에만 전진을 합니다.
  • -> 전체가 선형시간이 됩니다.

🔹 간단한 증명

• 고정길이의 합

sum[i ... i+K-1] -> sum[i+1 ... i+K]

: 위 변화 시 변동되는 내용은 아래와 같습니다.

-a[i] + a[i+K]

: 이 갱신을 모든 i에 대해서 반복하면 전체 합들이 정확히 계산됩니다(수학적 귀납법 가능).

 

• 가변 길이 (양 포인터)
  • 각 인덱스는 왼쪽/오른쪽 포인터에 의해 최대 한 번씩 만 증가합니다.(뒤로 가지 않음).
  • 불변식(제약 만족)을 유지하므로 놓치는 구간이 없으며 더 짧거나 더 좋은 해를 발견하면 갱신합니다.
  • 이렇게 하면 모든 가능한 후보 구간을 중복없이 커버할 수 있습니다.
• 슬라이딩 최댓/최솟값 (단조 deque)
  • deque에는 윈도우 안의 유효 후보만 남깁니다.
  • 즉, 윈도우가 이동해서 값이 윈도우 밖으로 나가게 되면 앞에서 제거, 뒤에서 더 크거나 작은 값에 의해 정답이 좌우되면 제거합니다. 
  • 따라서 각 인덱스는 최대 한 번 push와 최대 한 번 pop을 하게 되며, 따라서 선형시간으로 진행이 됩니다.

 

---

슬라이딩 윈도우 - 시간복잡도

---

🔹 간단한 시간복잡도 계산

• 고정 길이:
  • 초기합 O(K)에, 윈도우 슬라이드를 N - K번 진행하며, * O(1) 갱신이 됩니다.
  • -> O(N)
• 가변 길이:
  • 포인터 두 개가 오직 증가만 진행됩니다. 즉, 각 포인터는 최대 N회 이동합니다.
  • -> O(N)
• 단조 deque
  • 각 인덱스의 삽입/삭제가 각각 한 번 이하로 일어납니다.
  • -> 총 연산 O(N)

따라서 슬라이딩 윈도우로는 약 O(N)정도의 시간복잡도로 연산을 진행할 수 있습니다!

조건만 맞으면 정말 시간복잡도에서 유리한 알고리즘이지요!?

---

 

 

 

 

 

 

 

---

예제 문제 풀이: BOJ 2559 수열

---

* 예제 문제: BOJ 2559 수열

https://www.acmicpc.net/problem/2559

 

🔹 문제 설명

1. 매일 측정한 '온도' 값이 존재할 때,

2. 연속적인 몇 일의 합이 가장 큰 값을 구하는 문제입니다.

이 때, 연속적인 일자 수는 주어집니다.

 

🔹 입력 및 조건

온도 측정한 일 수인 N과 합을 구할 연속일수 K가 주어집니다.

N은 측정한 온도를 저장할 배열 크기로 쓰입니다.

이 때, N의 범위는 2~100,000이므로 선형탐색 O(N)으로 푸는 것이 유리합니다(O(N^2)시 시간초과 가능성).

K는 1~N사이 범위의 정수입니다.

 

다음으로 측정한 온도들이 순서대로 주어집니다.

이 때 온도들은 일자별로 순서대로 탐색이 필요하기 때문에 입력 순서대로 배열에 저장해줍니다.

온도는 -100~100사이의 숫자입니다.

따라서 100 * 100000 = 10,000,000 (1천만)으로, 최대 값을 더해도 int 범위내로 계산이 가능합니다.

 

🔹 출력

입력되는 온도 수열에 대해서 연속되는 k일 온도의 합이 최대가 되는 '값'을 출력하면 됩니다.

 

🔹 해결 과정

문제에서 주어진 '연속 일자 수'가 바로 window의 길이가 됩니다.

고정 길이의 슬라이딩 윈도우로써, window를 오른쪽으로 한 칸씩 이동시키면서 해당 범위의 누적 합을 구합니다.

누적 합을 선형으로 '기록된 온도 배열'을 모두 탐색을 마쳤을 때의 최대 누적합을 구하면 되는 문제입니다!

어렵지 않게, 모든 값들을 입력 받은 후, 온도를 저장한 배열을 K크기의 window로 선형탐색을 하면 되는 문제입니다.

window를 배열을 따라 이동하면 되므로 인덱스 값을 사용해서 고정 크기(i-k~i번째 원소의 합)으로 탐색하였습니다.

한 칸을 이동하면 앞의 값을 제외하고, 뒤의 값(큰 인덱스)을 더해줬습니다.

int maxSum = nowSum;
        for(int i = K; i < N; i++){
            nowSum += arr[i]; // 새로운 인덱스의 값 더하기
            nowSum -= arr[i - K]; // 앞 인덱스의 값 빼기
            maxSum = Math.max(maxSum, nowSum); // 현재 window의 합과 이전 window의 합 비교
        }

간단한 고정길이 sliding window

비교적 간단한 문제로, sliding window의 그림을 그려볼 수 있는 문제였습니다 !

 

🔹 전체 소스 코드

https://github.com/hwlee0103/algorithm-java/blob/master/BOJ/src/baekjoononline/slidingwindow/silver/boj2559Sequence.java

algorithm-java/BOJ/src/baekjoononline/slidingwindow/silver/boj2559Sequence.java at master · hwlee0103/algorithm-java

전체 소스코드는 위 깃헙 링크에 업로드 해 두었습니다!!

필요시 참고 부탁드려요~

---

이렇게 슬라이딩 윈도우에 대해서도 정리를 해보았는데요,

자료구조를 어떻게 쓰느냐에 따라서 투포인터랑 거의 비슷하다고 볼 수 있겠네요!

 

무엇보다 조건만 맞으면 시간복잡도가 O(N)인게 매력적이었습니다 ㅎㅎ

투포인터도 정리하려고 하는데, 그 땐 어떤 차이가 있는지도 한 번 공부해보겠습니다 !! :)

알고리즘 공부하는 우리 모두 화이팅입니다 ~~