투포인터(Two Pointer) 알고리즘

 

 

 

투포인터(Two Pointer)알고리즘

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

 

특징 1) 각 원소마다 모든 값을 순회해야할 때 사용

특징 2) 연속하다는 특성을 이용해서 철

특징 3) 두 개의 포인터(커서)가 움직이면서 계산

특징 4) 처음부터 생각하기 어려움 -> 쉬운 방법부터 생각하기

 

 

 

 

투포인터 알고리즘의 과정

 

1. 시작점(start)과 끝점(end)이 첫 번재 원소의 인덱스(0)를 가리키도록 한다.

 

2. 현재 부분 합이 M과 같다면 카운트한다.

 

3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.

 

4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.

 

5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

 

 

소스코드

# 데이터의 개수 N
n = 5
# 찾고자 하는 부분합 M
m = 5
# 전체 수열
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
  
  # 부분합이 m일 때 카운트 증가
  if interval_sum == m :
    count += 1
  interval_sum -= data[start]

print(count)