[알고리즘] 슬라이딩 윈도우 알고리즘(feat. Java)

슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘은 1차원 배열을 2회 이상 반복 탐색해야 할 때의 문제점인 시간복잡도(O(n^2))를 O(n)으로 줄일 수 있는 유용한 알고리즘이다.

 

이름처럼 1차원 배열에서 고정된 윈도우 사이즈만큼의 부분 배열이 특정 조건을 일치하는 지 처음부터 끝까지 슬라이딩하며 탐색하는 알고리즘인 것이다.

 

슬라이딩 윈도우 알고리즘의 경우, 윈도우 사이즈가 고정적이기 때문에 구현을 하는 것도 쉽다. 간단하게 단계를 서술하면 다음과 같다.(아래 그림 참고)

 

• 윈도우 사이즈만큼의 배열의 값들을 집어넣음(list, queue, ...)
• 배열의 오른쪽으로 한칸 슬라이드
• 슬라이드 되었으므로 부분배열의 첫부분은 삭제, 추가된 부분의 값 추가

 

 

 

문제풀이를 통한 코드 이해

풀이할 문제는 프로그래머스 사이트의 Lv3 징검다리 건너기 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

 

입력으로 주어지는 값은 징검다리의 가중치들의 배열과 최대로 뛰어넘을 수 있는 징검다리의 개수이다. 한명이 건널 때마다 징검다리의 가중치들이 줄어든다고 하였을 때 최대한 건널 수 있는 인원이 몇 명인지를 구하는 문제이다.(자세한 설명 위의 링크 참조)

 

이 문제는 슬라이딩 윈도우를 이용하면 풀면 효율성과 정확성 둘 다 쉽게 챙길 수 있는 문제이다. 먼저 코드를 살펴보겠다.

 

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public class Stone { 
        int idx;    //징검다리가 위치한 배열의 idx
        int num;    //징검다리의 가중치

        Stone(int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }
    public int solution(int[] stones, int k) {
        int answer = stones[0];
        Deque<Stone> dq = new LinkedList<>();    //부분배열을 저장할 deque선언
        
        dq.add(new Stone(0, stones[0]));    //초기값 세팅
        
        for(int i = 1; i < stones.length; i++) {
            if(dq.peekLast().num <= stones[i]) {    //현재 징검다리가 이전 징검다리보다 클 경우
            
                if(dq.peekFirst().num <= stones[i]) {//부분배열의 첫번째 값보다도 크면 부분배열 초기화
                    dq.clear();
                } 
                else {
                    while(dq.peekLast().num <= stones[i]){ //현재 징검다리보다 작은 값은 모두 poll
                        dq.pollLast();
                    }
                }
            }
            dq.add(new Stone(i, stones[i])); //현재 징검다리 값 부분배열 저장
            
            if(dq.peekFirst().idx <= i - k) { //부분배열의 처음값이 윈도우 사이즈 초과시 poll
                dq.pollFirst();
            }

            if(i < k) // 현재의 index가 k보다 작을 경우에는 max
                answer = Math.max(answer, stones[i]);
            else  // index가 k보다 클 경우에는 min
                answer = Math.min(answer, dq.peekFirst().num);
        }

        return answer;
    }
}

 

간단한 원리를 설명하면,

• 윈도우 사이즈만큼의 부분배열에서는 그 중 젤 큰 값만큼 건널 수 있다.
• 부분배열에서 젤 큰 값들을 모았을 때 그 중 젤 작은 값만큼이 전체 배열을 건널 수 있다.

특정 구간1에서는 7명이 건널 수 있지만 다른 특정 구간2에서는 3명만 건널 수 있다면, 전체 배열에서는 3명만 건널 수 있는 것이다. (7명 중 3명만 특정 구간 2를 지나갈 수 있으므로)

 

 

위의 문제 풀이만 봐서는 바로 응용하는 것이 힘들 수 있기 때문에 아래의 문제들을 푼다면 익히는데 도움이 될 것이다.

 

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

www.acmicpc.net/problem/2075

2075번: N번째 큰 수