[알고리즘] 슬라이딩 윈도우 알고리즘

 

슬라이딩 윈도우 알고리즘

 

이름만 들어도 참 길다.

하지만, 그 이름 자체에 모든 의미가 내포되어있다.

 

슬라이딩 윈도우 기법이란 2개의 포인터로 범위를 지정한 후에 그 범위를 유지한 채로 이동하며 문제를 해결한다.

 

투 포인터 알고리즘과 비슷하고 그 사용법 또한 어렵지 않다.

그렇다면 왜 사용하는가?

개인적으로는 탐색에 있어 좋은 효율을 보여주기 위해. 그리고 사고의 단순화를 위해서라고 생각이 든다.

 

슬라이딩 윈도우 기법은 쉽지만, 무엇과 어떻게 활용할 수 있냐에 따라 그 난이도가 달라진다.

아래 예시 코드로 슬라이딩 윈도우 기법의 예시를 살펴보자.

 

 

일반적인 슬라이딩 윈도우 기법

 

해당 문제는 백준 12891번 문제로, 일반적으로 슬라이딩 윈도우 기법을 사용하는 경우다.

12891번: DNA 비밀번호

탐색에 있어 슬라이딩 윈도우 기법을 사용하고,  슬라이싱 된 배열에 대한 카운트 처리에 대한 방법을 배울 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] checkArr;
    static int[] myArr;
    static int checkSecret;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int Result = 0;
        char A[] = new char[S];
        checkArr = new int[4];
        myArr = new int[4];
        checkSecret = 0;

        A = bf.readLine().toCharArray();
        st = new StringTokenizer(bf.readLine());
        for(int i=0; i<4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if (checkArr[i] == 0) {
                checkSecret++;
            }
        }

        for (int i=0; i<P; i++) {
            Add(A[i]);
        }

        if (checkSecret == 4) {
            Result++;
        }

        for(int i=P; i<S; i++) {
            int j = i-P;
            Add(A[i]);
            Remove(A[j]);
            if (checkSecret == 4) {
                Result++;
            }
        }

        System.out.println(Result);
        bf.close();
    }

    private static void Add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0]) {
                    checkSecret++;
                }
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == checkArr[1]) {
                    checkSecret++;
                }
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == checkArr[2]) {
                    checkSecret++;
                }
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == checkArr[3]) {
                    checkSecret++;
                }
                break;
        }
    }

    private static void Remove(char c) {
        switch (c) {
            case 'A':
                if (myArr[0] == checkArr[0]) {
                    checkSecret--;
                }
                myArr[0]--;
                break;
            case 'C':
                if (myArr[1] == checkArr[1]) {
                    checkSecret--;
                }
                myArr[1]--;
                break;
            case 'G':
                if (myArr[2] == checkArr[2]) {
                    checkSecret--;
                }
                myArr[2]--;
                break;
            case 'T':
                if (myArr[3] == checkArr[3]) {
                    checkSecret--;
                }
                myArr[3]--;
                break;
        }
    }
}

 

💡 전체 문자열에서 부분 문자열을 탐색해야 할 때, Add와 Remove 메서드를 통해 부분 문자열의 길이는 유지하고, 조건을 체크해 줄 수 있다.

💡checkArr와 myArr, 그리고 checkSecret라는 배열과 전역 변수를 통해 조건을 검토할 수 있다

 

 

슬라이딩 윈도우 기법의 활용 with Deque

 

탐색만 한다면, 굉장히 쉬울 것이다. 하지만, 이 슬라이딩 윈도우 기법의 진정한 효과는 Deque와 함께 사용할 때 나타난다.

 

이 때 Deque란 무엇인가?

Deque는 양방향 큐로 양쪽에서 엘리먼트를 추가하거나 제거할 수 있다.

 

 

만약, 전체 배열에서 각각의 부분 배열에 최솟값을 찾아야 할 때를 생각해보자.

이 때 최솟 값을 찾는 알고리즘, 즉 일반적인 정렬 알고리즘을 도입할 때 nlog(N)이라는 시간복잡도가 소요된다.

그래서 범위가 커진다면, 시간 복잡도 면에서 큰 손해를 볼 수 밖에 없다.(이를 노린 문제들도 많다.)

 

슬라이딩 윈도우 기법과 Deque를 함께 사용한다면, 부분 배열에서 최솟 값을 찾는데 O(N)의 시간복잡도밖에 들지 않는다.

그 아이디어는 아래와 같다.

 

💡 Deque의 첫번째 요소에 항상 최솟값을 둔다고 생각하자.

💡새롭게 들어오는 값과 Deque의 마지막 요소와 비교하며, 가장 작은 값이 첫 번째 요소가 올 수 있도록 한다.

💡 슬라이딩 윈도우 기법을 통해 맨 앞과 맨 뒤의 요소의 간격을 항상 유지해준다.(Add와 Remove)

 

 

관련된 예시 문제는 백준 11003번 문제이다.

11003번: 최솟값 찾기

 

아래는 풀이 예시이다.

 

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        Deque<Node> mydeque = new LinkedList<>();

        for (int i=0; i<N; i++) {
            int now = Integer.parseInt(st.nextToken());

            while(!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(i, now));

            if (mydeque.getFirst().index <= i-L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value+ " ");
        }
        bw.flush();
        bw.close();


    }

    static class Node {
        public int index;
        public int value;

        Node (int index, int value) {
            this.index = index;
            this.value = value;
        }
    }
}

 

 

💡 BufferedReader와 BufferedWriter를 통해서 버퍼를 사용해 입출력 상의 속도를 최적화 한다.

💡 Deque의 요소를 Node로 두어 index와 value를 사용할 수 있도록 한다. 이는 추가적인 조건을 만족하기 쉽게 한다.

💡 주어진 범위에서 벗어난다면, 첫 번째 요소를 삭제하여 이를 맞춰준다.(슬라이딩 윈도우 기법)

 

 

Reference

- Do it! 코딩 테스트 - 기초 편