알고리즘 - 슬라이딩 윈도우

슬라이딩 윈도우란?

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.

알고리즘 관련 서적에서는 알려져 있지 않으나, 네트워크에서 주로 사용되던 알고리즘을 문제 풀이에 이용한 것이라 할 수 있다.

이는 투 포인터와 함께 알고리즘 문제 풀이에서 유용하게 사용될 수 있다. 

이 둘의 개념이 유사해보일 수 있지만, 보통 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우라고 구분하면 좋다. 또한, '정렬된 배열을 대상'으로 하는 투 포인터와 달리 슬라이딩 윈도우는 '정렬 여부에 관계 없이' 활용된다는 차이가 있다.

 물론 교과서에 정의된 내용이 아니기 때문에 실무에서 주로 이런 형태로 쓰일 뿐, 때로는 서로 혼용되어 쓰이기도 한다. 

 

 

슬라이딩 윈도우와 투 포인터 비교

 

이름	정렬 여부	윈도우 사이즈	이동
투 포인터	대부분 O	가변	좌우 포인터 양방향
슬라이딩 윈도우	X	고정	좌 또는 우방향

 

슬라이딩 윈도우는 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하는 네트워크 용어이기도 하다.네트워크에서 패킷을 전송할 때 고정 사이즈의 윈도우가 옆으로 이동하면서 그 다음 패킷들을 전송하는 방식을 말하는데, 지금까지 설명한 슬라이딩 윈도우 알고리즘의 행동 패턴과 동일하기 때문에 슬라이딩 윈도우 명칭은 여기서 유래한 것으로 추측할 수 있다.

 

그렇다면 이제 실습을 해보자. 때로는 투 포인터와 서로 혼용되어 풀이하는 경우가 있는데, 둘 사이를 명확히 구분할 필요는 없기 때문에 같이 풀이해보자!

 

 

리트 코드 239번 문제

Q. 배열 nums가 주어졌을 때, k 크기의 슬라이딩 윈도우를 오른쪽 긑까지 이동하면서 최대 슬라이딩 윈도우를 구하라.

 

입력

nums = [1,3,-1,-3,5,3,6,7], k=3

출력

[3,3,5,5,6,7]

 

 

리트코드 76번 문제

Q. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.

 

입력

S = "ADOBECODEBANC", T = "ABC"

출력

"BANC"

 

def solution(S,T):
    need = collections.Counter(T)
    missing = len(T)
    left = start = end = 0
    
    # 오른쪽 포인터 이동
    for right, char in enumerate(S,1):
    	missing -= need[char] > 0 #와우...
        need[char] -= 1
        
        # 필요 문자가 0이면 왼쪽 포인터를 이동시킴
        if missing == 0:
             while left<right and need[S[left]] < 0:
                need[S[left]] += 1
                left += 1
                
             if not end or right - left <= end - start:
            	start, end = left, right
                
            need[S[left]] += 1
            missing += 1
            left += 1
    return S[start:end]

 

 

 

출처

파이썬 알고리즘 인터뷰 - 책만

https://github.com/onlybooks/algorithm-interview