[알고리즘/Kotlin]슬라이딩 윈도우(Sliding Window) 알고리즘

 

슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)이란?

연속적인 구간의 문제를 효과적으로 해결하기 위한 알고리즘

이 알고리즘은 일정한 크기의 윈도우를 이용하여 연속적인 구간 문제를 해결

 

슬라이딩 윈도우 알고리즘 구현 단계 

1. 시작점과 끝점을 초기화합니다.
2. 윈도우의 크기를 설정합니다.
3. 윈도우를 이동하면서 구간의 값을 계산합니다.
4. 구간의 값을 이용하여 원하는 결과를 도출합니다.
5. 끝점이 배열의 마지막 인덱스에 도달할 때까지 위 과정을 반복합니다.

슬라이딩 윈도우 알고리즘  사용 예

배열에서 최소값을 찾는 문제

문자열에서 최소 윈도우를 찾는 문제

스트림에서 슬라이딩 윈도우를 적용하여 데이터를 처리하는 문제 등에 사용

 

2023.02.26 - [프로그래머스/Kotlin]Level3 - 징검다리 건너기

이 문제가 대표적인 슬라이딩-윈도우를 사용하는 문제.

(나는 슬라이딩-윈도우를 모를 때, 비슷한 방법으로 풀었다가 실패했다 :: 풀이2)

 

슬라이딩 윈도우 알고리즘은 윈도우의 크기를 조정하면서 문제를 해결하므로, 일반적으로 시간 복잡도가 선형이 된다.

따라서, 데이터 크기가 큰 문제에 대해서도 효과적인 알고리즘이다.

 

Sample Code

fun slidingWindow(arr: IntArray, k: Int): IntArray {
    val result = IntArray(arr.size - k + 1)
    var sum = 0
    for (i in 0 until k) {
        sum += arr[i]
    }
    result[0] = sum
    for (i in k until arr.size) {
        sum += arr[i] - arr[i - k]
        result[i - k + 1] = sum
    }
    return result
}

위 코드는 정수 배열 arr과 윈도우 크기 k를 인자로 받아서 슬라이딩 윈도우를 적용한 결과를 반환하는 함수이다.

반환값은 각 윈도우의 합을 저장한 정수 배열이다.

이 함수의 내용을 간단히 설명하자면, 첫 번째 반복문에서는 처음부터 k까지의 합을 구하여 sum 변수에 저장한다.

이후, 두 번째 반복문에서는 윈도우를 이동하면서 sum 변수를 갱신하고, 결과 배열에 합을 저장한다.

반환값으로 결과 배열을 반환한다.

 

예를 들어, 다음과 같이 함수를 호출할 수 있다.

val arr = intArrayOf(1, 3, -1, -3, 5, 3, 6, 7)
val k = 3
val result = slidingWindow(arr, k)
println(result.joinToString()) // 출력: "3 5 1 7 11 14"

위 코드는 arr 배열에 대해 크기가 3인 윈도우를 적용한 결과를 출력.

출력 결과는 3 5 1 7 11 14