[PS] 슬라이딩 윈도우

Hood·2024년 11월 2일

Sliding Window ps

PS

목록 보기

4/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

들어가기 전에

앞서 살펴본 투 포인터는 배열에서 특정 구간이 조건에 맞는지 확인할 때 자주 사용하는 알고리즘입니다.
단순히 누적합만으로 모든 구간을 확인하면 결국 많은 경우의 수를 직접 탐색해야 하므로,
최종 시간 복잡도가 O(N²) 이 되는 경우가 많습니다.

하지만 모든 구간이 아니라, 길이가 고정된 구간만 확인하면 되는 문제도 있습니다.
이럴 때 자주 사용하는 방법이 바로 슬라이딩 윈도우(Sliding Window)입니다.

슬라이딩 윈도우

슬라이딩 윈도우는 말 그대로 고정된 크기의 창(window) 을 배열 위에서 한 칸씩 이동시키며 원하는 값을 찾는 알고리즘입니다.

이 알고리즘의 핵심은 윈도우의 크기가 고정되어 있다는 점입니다.
즉, 구간의 길이가 계속 달라지는 것이 아니라 항상 같은 크기를 유지한 채 이동합니다.

예를 들어 배열에서 길이가 x인 연속 구간만 확인해야 한다고 해보겠습니다.
이 경우에는 현재 구간을 유지한 채, 왼쪽 값을 하나 빼고 오른쪽 값을 하나 더하면서 다음 구간으로 이동하면 됩니다.

이런 방식은 사실상 고정 길이 구간을 다루는 특수한 형태의 투 포인터라고 볼 수 있습니다.
투 포인터에서는 시작점과 끝점을 상황에 따라 다르게 움직이지만,
슬라이딩 윈도우에서는 두 포인터가 항상 함께 한 칸씩 이동합니다.

즉, 두 개의 포인터를 따로 복잡하게 다루기보다
현재 구간합을 갱신하는 방식으로 훨씬 간단하게 구현할 수 있습니다.

예를 들어

배열에서 연속된 3개의 합을 구해야 하는 경우를 생각해 보겠습니다.

처음에는 앞에서부터 3개를 선택해 합을 구합니다.
그다음 다음 구간으로 이동할 때는, 이전 구간의 맨 앞 값은 빼고
새롭게 포함되는 맨 뒤 값은 더해 주면 됩니다.

예를 들어 현재 구간이 다음과 같다면,

(1, 2, 3) → 합 6

다음 구간 (2, 3, 4)의 합은
기존 합 6에서 1을 빼고 4를 더하면 됩니다.

즉,

6 - 1 + 4 = 9

이런 식으로 이전 계산 결과를 재사용할 수 있기 때문에
매번 구간 전체를 다시 더할 필요가 없습니다.

이 과정에서 실제로는 현재 윈도우의 끝을 가리키는 인덱스 하나만 잘 관리해도 충분합니다.
새로운 값이 들어오면 더하고, 윈도우 범위를 벗어나는 값은 빼 주면 되기 때문입니다.

Kotlin

위 예시를 Kotlin 코드로 구현하면 다음과 같습니다.

fun main() {
    val x = 3
    val arr = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    var sum = 0

    repeat(x) {
        sum += arr[it]
    }

    var ans = sum

    for (y in x until arr.size) {
        sum += arr[y] - arr[y - x]
        if (ans < sum) {
            ans = sum
        }
        println(ans)
    }
}

이 코드를 순서대로 보면 다음과 같습니다.

먼저 윈도우의 크기 x를 정합니다.
사용할 배열 arr를 준비합니다.
첫 번째 구간(0부터 x - 1까지)의 합을 미리 구해 sum에 저장합니다.
ans에는 현재까지의 최댓값을 저장합니다.
반복문을 돌면서 새로 들어오는 값 arr[y]를 더하고, 윈도우에서 빠지는 값 arr[y - x]를 뺍니다.
갱신된 sum이 기존 최댓값보다 크다면 ans를 갱신합니다.

즉, 매번 구간 전체를 다시 더하는 것이 아니라
이전 구간합을 바탕으로 다음 구간합을 O(1)에 갱신하는 것이 핵심입니다.

다만 위 코드는 매 반복마다 ans를 출력하고 있으므로,
문제에 따라 최종 결과만 필요하다면 반복문이 끝난 뒤 한 번만 출력해도 됩니다.

예를 들면 아래처럼 작성할 수 있습니다.

fun main() {
    val x = 3
    val arr = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

    var sum = 0
    repeat(x) {
        sum += arr[it]
    }

    var ans = sum

    for (y in x until arr.size) {
        sum += arr[y] - arr[y - x]
        ans = maxOf(ans, sum)
    }

    println(ans)
}