투 포인터(Two Pointer)

투포인터 알고리즘이란?

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

예를 들어보면,

한 반에 학생들이 40명이 있을 때, 모든 학생을 번호순서대로 일렬로 세운뒤, 순차적으로 지목한다고 생각해보자

2,3,4,5,6,7번 학생을 부를때, 2번부터 7번까지의 학생 이라고 부를 수도있는데, 이처럼 시작점과 끝점을 사용하여 데이터의 범위를 표현할 수 있다.

 

• 시작점(start)과 끝점(end)이 첫번째 원소의 양 끝점을 가르키도록 한다.
• 현재 부분합이 구하고자 하는 값과 같다면 카운트한다
• 현재 부분합이 구하고자 하는 값보다 작다면, end를 1증가(구간합이 감소)
• 현재 부분합이 구하고자 하는 값보다 크다면 start를 1증가(구간합 증가)
• 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

투포인터를 가르키는 방식은 다양한 방법이있는데, start,end를 index = 0일때부터 시작하는 방법도 존재한다.

 

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1,2,3,2,5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키면서 반복
for start in range(n):
	#end를 이동시킬 수 있는 만큼 이동
    while interval_sum <m and end < n : 
    	interval_sum +=data[end]
        end+=1
    
    if interval_sum == m :
    	count+=1
    interval_sum -=data[start]
print(count)