자료구조와 알고리즘 - 슬라이딩 윈도우(Sliding Window)

 

 

 

---

1. 슬라이딩 윈도우 개념

 

 슬라이딩 윈도우(슬라이딩 창)는 원래 데이터 처리와 통신에서 사용되는 기법으로 언급된다. 고정된 크기의 윈도우(창)를 사용하여 데이터를 처리하는 방식을 나타낸다. 이 기법은 주로 통신 프로토콜에서 오류 제어, 흐름 제어, 데이터 전송 등에 활용된다.

 

 코딩테스트와 알고리즘에서는 슬라이딩 윈도우가 배열 또는 리스트에서 고정된 크기의 부분 배열을 효율적으로 처리하는 데 활용되는 개념으로도 사용된다. 특히 연속적인 부분 배열의 합이나 패턴을 찾는 등의 문제에서 슬라이딩 윈도우를 적용하여 코드를 최적화하는 경우가 있다.

 

 

 

 

 

2. 예시 문제

https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

s,p = [int(i) for i in input().split()]
strings = input()
condition = [int(i) for i in input().split()]

#hashmap
hash_map = {"A":0,"C":0,"G":0,"T":0}
idx = 0
for k in hash_map.keys():
    hash_map[k] = condition[idx]
    idx += 1

#check 
answer = 0
def check(answer,hash_map):

    flag = True

    for v in hash_map.values():
        if v > 0:
            flag = False
            break
    if flag:
        answer += 1

    return answer

#sliding window init
l = 0
r = p-1
arr = strings[l:r+1]

for k in arr:
    hash_map[k] -= 1
answer = check(answer,hash_map)

l += 1
r += 1

#sliding window
while r < s:

    front = strings[l-1]
    rear = strings[r]

    hash_map[front] += 1
    hash_map[rear] -= 1
    
    answer = check(answer, hash_map)

    l += 1
    r += 1

print(answer)

 

위 문제는 DNA 문자열에서 주어진 부분문자열의 길이와 각 문자의 최소 등장 횟수가 주어질 때, 조건을 만족하는 서로 다른 부분문자열의 종류 수를 구하는 것이다. 

여기서 "CCTGGATTG"를 슬라이딩 윈도우 개념을 활용하여 앞에거, 뒤에거만 빼고 더함으로써 문제를 효율적으로 해결할 수 있다.

 

 

 

 

 

---