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

 

 

1.  개념

         

           슬라이딩 윈도우 : 투 포인터를 이용해 범위를 지정해주고 지정된 범위를 옮겨가면서 문제를 해결하는 알고리즘

            * 지정된 범위 : window  옮기기 : sliding

 

 

2.  문제 풀이

 

# 1  DNA 비밀번호 - 백준 12891번

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

12891번: DNA 비밀번호

 

 

 

 

import sys 
input = sys.stdin.readline 

ans = [0] * 4
now = [0] * 4

# 윈도우 옮길 때 추가되는 원소의 now값 +1

def plus(end):
    
    global cnt, now, ans
    if end == "A":
        now[0] += 1
        
    elif end == "C":
        now[1] += 1
    
    elif end == "G":
        now[2] += 1
        
    elif end == "T":
        now[3] += 1

# 윈도우 옮길 때 빠지는 원소의 now값 -1
def minus(start):
    
    global cnt, now, ans
    
    if start == "A":
        now[0] -= 1
    elif start == "C":
        now[1] -= 1
    elif start == "G":
        now[2] -= 1
    elif start == "T":
        now[3] -= 1
        
    
s,p = map(int,input().split())
dna = list(input())
ans = list(map(int,input().split()))

start = 0
end = p-1

result = 0

# 초기 윈도우의 now 값
for i in range(p):
    plus(dna[i])

# now의 모든 값이 ans의 모든 값보다 크거나 같을 때 result +1
if now[0]>=ans[0] and now[1]>=ans[1] and now[2]>=ans[2] and now[3]>=ans[3]:
    result += 1

# 윈도우 한 칸씩 옮기기
while end <= s-2:
    minus(dna[start])
    start += 1
    end += 1
    plus(dna[end])
    
    # now의 모든 값이 ans의 모든 값보다 크거나 같을 때 result +1
    if now[0]>=ans[0] and now[1]>=ans[1] and now[2]>=ans[2] and now[3]>=ans[3]:
        result += 1
    

print(result)

 

 

 

 

 

 

# 2  최솟값 찾기 1 - 백준 11003번

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

11003번: 최솟값 찾기

 

 

이건 아직 무리인 듯하다..