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

1. 투 포인터(Two Pointers) 알고리즘

• 배열의 특정 연속된 구간을 처리하는 경우 사용
• 리스트에 순차적으로 접근해야 할 때, 두개의 점을 이용해 위치를 기록하면서 처리하는 기법
• $O(N)$

2. 예시 문제

• [1,2,3,2,5]
• 합이 5 인 부분 연속 수열의 개수 구하시오
  • 각 지점에서 구간을 늘려가며 연속되는 수를 확인하는 방법?
    • 시간 복잡도 : $O(n^2)$
    • 데이터의 개수가 많아지면 시간이 많이 걸림
  • $O(N)$으로 풀려면?
    • 투 포인터 알고리즘 사용하기

3. 풀이

• start, end 포인터를 첫 번째 인덱스를 가리키도록!
• 합이 5보다 작으면 end 오른쪽으로 이동 (합을 늘림)
• 합이 5보다 크면 start를 오른쪽으로 이동 (합을 줄임)
• 합이 5가되면 count, start를 오른쪽으로 이동

#데이터의 개수 N과 부분 연속 수열의 합 M을 입력 받기
n, m = 5,5
data = [1,2,3,2,5]

result = 0
summary = 0
end = 0

#start를 차례대로 증가시키며 반복
for start in range(n):
    #end를 가능한 만큼 이동시키기
    while summary < m and end <n:
        summary += data[end]
        end +=1
    #부분 합이 m일 때 카운트 증가
    if summary == m:
        result+=1
    summary -=data[start]

print(result)

4. 참고

https://www.youtube.com/watch?v=rI8NRQsAS_s