[알고리즘] 슬라이딩 윈도우 패턴(Sliding Window -java)

[알고리즘 기초] 슬라이딩 윈도우 패턴(Sliding Window -java)

JavaScript (JS) Algorithms and Data Structures Masterclass | Udemy
해당 포스팅은 JavaScript 알고리즘 & 자료구조 마스터클래스강의를 참고하여 작성했습니다.

슬라이딩 윈도우 패턴은 배열이나 문자열 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 데이터의 하위 집합을 찾는 경우에 유용하게 사용합니다.

예를 들어 가장 긴 고유 문자열을 찾는 함수를 작성하라고 하면
helloworld
다음과 같이 찾을 수 있습니다.
첫 번째는 hel,
두 번째는 low,
세 번째는 orld 입니다.
이때 orld가 가장 긴 고유 문자열 입니다.

 

 

슬라이딩 윈도우(Sliding Window)

주어진 배열에서 n개의 연속적인 숫자의 합계 중 제일 큰 값을 구하는 함수를 작성하시오.

예시)
[1, 2, 3, 4], n=2 -> 9
[2, 6, 9, 2, 1, 8, 5, 6, 3], n=3 -> 19
[1, 2, 3, 4, 1], n=3 -> 9

simpleMaxSubarraySum

먼저 중첩 loop를 사용하여 작성해보겠습니다.

int simpleMaxSubarraySum(int[] arr, int num) {
    if(num > arr.length) {
        return 0;
    }

    int max = Integer.MIN_VALUE;

    for(int i = 0; i < arr.length - num + 1; i++) {
        int sum = 0;
        for(int j = 0; j < num; j++) {
            sum += arr[i + j];
        }
        if(sum > max) {
            max = sum;
        }
    }
    return max;
}

이런 방식은 매우 비효율적 입니다.
arr의 크기, num의 크기에 따라서 loop를 계속 돌아야하기 때문 입니다.

maxSubarraySum

// O(N)
int maxSubarraySum(int[] arr, int num) {
    int maxSum = 0;
    int tempSum = 0;

    if(arr.length < num) {
        return 0;
    }
    // 첫 시작 위치 배열의 합 계산
    for(int i = 0; i < num; i++) {
        maxSum += arr[i];
    }

    // 교집합 정보 공유를 위함
    tempSum = maxSum;

    // 슬라이딩 윈도우
    for(int i = num; i < arr.length; i++) {
        // 윈도우 크기를 유지하면서
        // 기존 값에서
        // 새롭게 추가된 값은 더하고,
        // 필요없는 값은 뺀다.
        tempSum = tempSum - arr[i - num] + arr[i]; // 양쪽 끝 원소만 갱신
        maxSum = Math.max(maxSum, tempSum); // 최댓값 계산
    }

    return maxSum;
}

여기서 핵심은 처음 부터 모든 배열의 합을 구할 필요가 없다는 것 입니다.
기존 합에서 필요없는 배열의 값을 빼고 새롭게 추가된 배열의 값을 더하면 됩니다.

그림으로 보면 아래와 같습니다.

교집합의 정보를 공유하면서 양쪽 끝 원소만 갱신 합니다.

정리

• 첫 시작 위치의 배열을 계산
  • 교집합의 정보를 공유하기 위함
• 윈도우 크기를 유지하면서 탐색을 실행
  • 양쪽 끝 원소만 갱신