Sliding window와 Two pointer algorithm

Sliding window algorithm은 하나의 포인터, 윈도우 사이즈 변수가 필요하다.

윈도우 사이즈는 리스트 안에서 범위다.

아래는 길이가 5(n)인 리스트에서 길이가 3(k)인 연속된 최대 부분합을 구하는 코드다.

윈도우 사이즈(k)가 3을 채운 이후로 start번째 값을 빼주고 새로운 i번째 값을 더한다.

arr=[5, 2, -1, 0, 3]
n=5
k=3		# 윈도우 사이즈
start=0
ans=0
window_sum=0

for i in range(n) :
	window_sum+=arr[i]
	if i >= k-1 :
		ans=max(window_sum, ans)
		window_sum-=arr[start]
		start+=1

print(ans)

위 코드 실행과정

 

 

Two pointer algorithm은 두 포인터 start, end를 사용한다.

# 프로그래머스 '보석 쇼핑'문제 중에서
def solution(gems):
    answer=[1, len(gems)]
    size=len(set(gems))
    dic={}
    start=0
    end=0
    
    while end < len(gems) :
        if gems[end] in dic :
            dic[gems[end]]+=1
        else :
            dic[gems[end]]=1        # 추가
        end+=1
        
        if len(dic) == size :
            while start < end :
                if dic[gems[start]] > 1 :
                    dic[gems[start]]-=1
                    start+=1
                elif end-start < answer[1]-answer[0]+1 :
                    answer=[start+1, end]
                    break
                else :
                    break
                                    
    return answer

 

 

 

참고 👇

 

https://stackoverflow.com/questions/64078162/is-two-pointer-problem-same-as-sliding-window

Is two pointer problem same as sliding window

 

https://bbangson.tistory.com/72

[Java]투 포인터 / 슬라이딩 윈도우 알고리즘

 

https://www.geeksforgeeks.org/window-sliding-technique/

Window Sliding Technique - GeeksforGeeks

 

https://blog.fakecoding.com/archives/algorithm-slidingwindow/

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