Sliding Window 알고리즘

슬라이딩 윈도우 알고리즘이란?

 

고정된 사이즈의 윈도우를 이동시키면서 윈도우 내의 데이터를 이용해 문제를 푸는 알고리즘. 특정 범위 내의 값들을 비교할 때 사용할 수 있다. 

 

 

유사한 알고리즘으로는 투 포인터가 있는데, 투 포인터는 대개 정렬된 배열에 이용되며 부분 범위의 사이즈가 고정되어 있지 않다는 점에서 슬라이딩 윈도우와 다르다. 

 

 

 

글로만 봐서는 쉽게 이해하기 힘들 수 있기에 (나같은 경우에는 슬라이딩 윈도우 구현 코드를 보고도 한 번에 이해하기가 힘들었다.) 수월한 이해를 돕기 위해 구체적인 예시 문제를 가져와서 설명해보겠다.

 

 

 

 

예제: Leetcode 3. Longest Substring Without Repeating Characters

 

이 문제는 제목에서도 알 수 있듯이, string이 주어지면, 중복 character가 없는 가장 긴 substring의 length를 반환해야 하는 문제이다.

 

 

 

알고리즘 적용

 

1. 부분범위의 시작을 나타내는 index인 left와 끝을 나타내는 index인 right를 각각 둔다.

 

2. right를 하나씩 증가시키면서 left-right 사이의 부분 배열이 중복된 문자가 없는지 확인한다.

 

3. left-right 사이의 부분 배열이 중복문자를 포함하게 된다면, 중복 문자를 제외하도록 left를 증가시킨다.

 

4. right가 배열의 끝에 도달할 때까지 반복한다.

 

 

 

 

 

다음과 같이 문자열이 주어진다면 left와 right은 각각 0에서 시작하고, right가 하나씩 증가하며 새로운 문자가 left와 right 사이의 substring에 이미 존재하는 문자인지 확인할 것이다.

 

left = 0, right = 1인 상황. 시작하고 나서 right가 한 칸 이동한 이후의 모습

 

 

그러다가 substring 내에 이미 존재하는 문자를 right이 가리키게 된다면 left가 그 문자를 제외하는 위치로 이동해야 한다.

 

 

따라서 결과적으로 다음과 같은 위치로 이동하게 될 것이다.

 

 

 

이 문제에서는 부분범위가 고정되어 있지는 않는다는 점에서 슬라이딩 윈도우 알고리즘이 맞나 싶긴 하지만 리트코드에서 제공한 솔루션에 슬라이딩 윈도우 알고리즘이라고 소개되어 있으므로.. 그런 걸로 하자. 

 

 

 

 

 

 

구현 코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	//0으로 초기화하면 첫 번째 원소의 인덱스값과 같아지기 때문에 -1로 초기화
        vector<int> chars(128,-1);
        
        int left = 0;
        int right = 0;
        int res = 0;
        
        while(right < s.length()){
            char r = s[right];
            
            int index = chars[r];
            
            //index값이 substring 내에 속하면 중복된 char가 나왔다는 뜻이다.
            if(index >= left and index < right){
            	//이전에 먼저 나왔던 중복 char를 제외한다.
                left = index + 1;
            }
            
            res = max(res, right - left + 1);
            
            //chars에는 해당 char가 가장 최근에 발견된 index값을 저장한다.
            chars[r] = right;
            right++;
        }
        return res;
    }
};