[개념정리] 투 포인터, 슬라이딩 윈도우+구간합

SH·2024년 7월 10일

알고리즘

목록 보기

8/8

투 포인터 / 슬라이딩 윈도우 최종 정리

초기상태: s와 e 포인터를 각각 0으로 세팅
e 포인터

앞으로 구간에 들어갈 원소를 가리키고 있음(현재 e포인터가 가리키는 원소가 구간에 포함된게 아님).
문제 조건에 따라 해당 원소가 구간 내에 들어갈 수 있으면 포함시키고 e 포인터를 +1해줌
구간 내에 들어갈 수 없으면 포함시키지 않고 s포인터를 증가시켜서 맨 앞의 원소를 구간에서 빼줌. e포인터가 가리키는 원소가 들어갈 수 있을 때까지 s포인터를 계속 앞으로 땡기는거임

s 포인터

구간의 맨 처음 원소를 가리키고 있음.
e 포인터가 가리키는 원소가 구간에 들어갈 수 없다면 s포인터가 가리키고 있는 원소를 구간에서 빼주고 s+=1해줌

이 구간의 사이즈가 고정되어있는게 슬라이딩 윈도우고, 고정되어있지 않은게 투포인터임

투 포인터

구간의 양 끝을 가리키는 포인터를 둠
문제의 조건에 맞춰 구간 내 원소들이 조건에 맞지 않는다면 왼쪽 포인터를 1 증가시켜 구간 범위를 좁힘
조건에 충족한다면 최적화를 하기 위해 오른쪽 포인터를 1 증가시켜서 구간 범위를 넓히는 방식
투포인터도 이진탐색과 마찬가지로 left, right 포인터가 가리키는 것을 무엇으로 할지, 또한 해당 포인터들의 위치가 변하는 조건은 무엇인지, 어떻게 처리해야 하는지 명확히 기준을 세우고 문제 풀이를 진행하는 것이 중요하다
즉 투포인터도 이진탐색처럼 l과 r이 가리키는걸 무엇으로 지정할지, 언제 l을 증가시키고 언제 r을 증가시킬지 고민해야함

정의

여기서 l과 r 포인터가 가리키는 원소는 이미 범위에 포함된 것이 아니라, 범위에 포함할 지 말 지 결정하기 전이거나 조건이 충족되지 않아서 범위에 포함시키지 못해 대기하고 있는 상황임

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

ex) 2, 3, 4, 5, 6, 7번 학생을 지목할 때
-> 시작점 2와 끝점 7이라는 2개의 점으로 접근할 데이터의 범위 표현
-> 2번부터 7번까지 학생

시간복잡도

O(N)

동작 과정

초기세팅: 시작점과 끝점이 리스트의 첫번째 원소를 가리키도록 설정

아래 과정 반복

현재 부분합이 M과 같을 경우
-> 카운트
현재 부분합이 M보다 작을 경우
-> 부분합에 포함되는 원소를 늘려야 함
-> end를 1 증가시킴
현재 부분합이 M 보다 같거나 큰 경우
-> 부분합에 포함되는 원소를 줄여야함
-> start를 1 증가시킴

ex) 특정한 합을 가지는 부분 연속 수열 찾는 문제에 적용 가능

O(N) 시간복잡도를 갖는 방식으로 풀이하는 방법

예시 - 합이 5인 연속 수열 찾기

반복..

수도코드

count, interval_sum, end = 0, 0, 0 # 초기세팅
arr = [2, 3, 1, 4, 29, 3]

for a in arr: # 리스트의 원소를 돌면서
	# end를 가능한 만큼 오른쪽으로 이동
	while interval_sum이 M보다 작고 and end 포인터가 N보다 작을 때까지
    	interval_sum += end번째 원소의 값 누적
        end 1 증가
    
    # interval_sum이 M과 같은 경우
    if interval_sum이 M이라면
    	count 1 증가
    
    # interval_sum이 M 이상인 경우
   	interval_sum -= arr[start] # start번째 값 제외 (= start 포인터 오른쪽으로 한칸 이동)