슬라이딩 윈도우 알고리즘(Sliding window algorithm)

인사말

안녕하세요 태끼입니다 올해의 첫 포스팅이네요. 작년은 유독 기억에 남는 해가 아닐까 싶습니다. 생각해보면 참 열심히 살았고 그에 따라 얻는 것도 많았지만, 체력적/심적으로 많이 지치기도 했던 한 해였던 것 같아요. 작년에 대한 회고는 스스로 차분히 잘 해봤는데요. 작년을 거름 삼아 올해를 더 잘 보내는 데에 집중해보도록 하겠습니다 :)

올해에 저에게는 몇 가지 목표가 있는데요. 그중 한 가지는 코딩테스트(여러 가지 형태가 될 것 같아요!)에 응시해서 한 번이라도 통과하는 것입니다. 코딩테스트마다 조건이나 기준이 다를 테지만 공부한 만큼 성과를 이뤄내고 싶고 동기부여를 받고 싶어요. 여느 해보다는 좀 더 코딩테스트 준비에 힘쓸 예정이에요. 알고리즘 이론이나 새롭게 알게된 문법이나 스킬 등등도 종종 포스팅해보겠습니다!


서론이 너무 길었네요! ㅋㅋ 오늘은 슬라이딩 윈도우 알고리즘에 대해서 알아본 내용을 정리하고 기록해 놓으려고 합니다. 문제를 풀다 보니까 많이는 아니더라도 필요한 순간이 가끔 있어서 정리해보면 좋겠다 싶었습니다. 편한 말투로 적도록 하겠습니다.

---

슬라이딩 윈도우 알고리즘(Sliding window algorithm)

Sliding window algorithm(슬라이딩 윈도우 알고리즘)은 윈도우라고 불리우는 특정 구간을 이동시키면서, 특정 구간 내에 있는 데이터를 이용해서 문제를 풀이하는 알고리즘을 말한다.

가장 기본적인 상황을 같이 한번 살펴보자.

• N개의 원소를 가지는 배열
• W의 크기를 가지는 윈도우(= 구간)

이렇게 2가지의 재료가 있다고 가정해볼 것이다.
여기서 중요한 포인트는 N, W 모두 고정된 크기라는 점, 좌 · 우 한 방향으로 이동한다는 점이다.

예시로, 9개의 원소를 가지는 아래의 배열에서 K = 3 구간에서 나올 수 있는 최대 합을 구해보자.
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ]

[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 14
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 13
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 10
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 13
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 19
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 15
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 11
^^^^^^^^^^

사실 풀이 자체가 어려운 문제는 아니다. 1칸씩 옆으로 움직이면서 3개의 범위 안에 있는 숫자를 더해주고 최종적으로 최대 합을 구하면 되는 문제이기 때문이다.

let array = [7, 4, 3, 2, 5, 6, 8, 1, 2]
let k = 3 // 3인 구간

var sum = 0
for i in 0..<array.count {
	let prefixSum = array[i..<i+k].reduce(0, +)  // <- 이 부분에 대한 효율성이 요점이다.
	sum = max(sum, prefixSum)
}

기본적인 방법으로 구간합을 구하게 되면, K개의 숫자의 합을 구해야 하니까 시간 복잡도 O(K)가 도출된다. 그렇게 되면 전체 시간 복잡도는 O(N * K) (N은 배열의 크기)의 시간이 될 것이다. 그러나 이런 식으로 계산을 했을 때 시간 초과가 발생하는 상황이 생긴다. 이를 좀 더 효율적으로 개선할 수는 없을까?

let array = [7, 4, 3, 2, 5, 6, 8, 1, 2]
let k = 3 // 3인 구간

var prefixSum = array[0..<3].reduce(0,+) // 최초의 구간 합 -> 이 때는 어쩔 수 없이 계산을 해주어야 함

var sum = 0
for i in k..<array.count {
	prefixSum += array[i] - array[i - k] // 효율성을 개선할 수 있다.
	sum = max(sum, prefixSum)
}

교집합을 제외한 나머지 값에만 변화를 주는 방식으로 코드를 개선해볼 수 있다.

[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 14 // 1)
^^^^^^^^^^
[ 7 ] [ 4 ] [ 3 ] [ 2 ] [ 5 ] [ 6 ] [ 8 ] [ 1 ] [ 2 ] sum = 13 // 2)
^^^^^^^^^^
여기서 4, 3은 교집합이기 때문에 1)의 구간 합(14)에서 1) 구간의 첫번째 값만 빼주고, 2) 구간의 마지막 값만 더해주면 된다.

이렇게 되면 숫자 하나씩만 더하고 빼주는 상황이 성립되기 때문에 O(1)의 시간 복잡도를 가진다. 기존 전체 시간 복잡도 O(N * K)가 O(N)으로 개선되는 것이다. 차이가 안 나는 거 아닌가라는 생각이 들 수 있는데 K가 N과 같은 상황이 되면 O(N^2)과 O(N)으로 엄청난 차이가 발생한다.

---

메모

적절한 상황에서 이 알고리즘을 사용하게 되면 효율성 측면에서 장점을 기대할 수 있을 것이다.
다음과 같은 유형에서 사용한다고 한다.

유형

• 구간 합
• Anagram
• 구간 최소값, 최대값

투 포인터 알고리즘(Two pointers algorithm)과도 연계해서 많이 쓰이는 것 같은데 해당 알고리즘은 다음 시간에 다뤄보도록 하자. 이론 자체는 어렵지 않은데 적절한 상황에서 문제에 응용하는 것이 어려운 것 같다. 해당 알고리즘이 활용되는 문제를 몇 개 풀어보면서 체화하는 것이 중요할 것 같다.

---

예제

이 정도 풀어보면 감이 좀 잡힐 것 같다. 1번은 위에서 살펴본 개념을 그대로 적용하는 예제이고, 4번이 개념을 응용하는 문제이다.

1. 백준 - 꿀 아르바이트
2. 백준 - 블로그
3. LeetCode - 중복 없는 긴 문자열
4. 프로그래머스 - 추석 트래픽

---

혹시 틀린 내용이나 궁금한 점이 있으면 댓글 남겨주세요!
그리고 문제 풀이는 다음 레포지터리에서 진행하고 있습니다. 공부 잘하고 있나 궁금하시면 방문해주세요 ^__^

https://github.com/Taehyeon-Kim/SwiftAlgorithm

GitHub - Taehyeon-Kim/SwiftAlgorithm: 나 이제 진짜 Swift로 알고리즘 공부한다?