[Algorithm/Python] 투 포인터(Two Pointers) 알고리즘 정리

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

리스트에 담긴 데이터에 순차적으로 접근해야 할 때, 시작점(start)과 끝점(end) 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

 

특정한 합을 가지는 부분 연속 수열 찾기

- N개의 자연수로 구성된 수열이 있다.
- 합이 M인 부분 연속 수열의 개수를 구해보자.
- 수행 시간 제한은 O(N)이다.

 

이미지 출처: 이것이 코딩테스트다 with python

 

위 문제는 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다.

 

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

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

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

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

 

# 구현 코드

n = 5
m = 5
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

for start in range(n):
	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)