투 포인터(Two-pointer) 알고리즘이란?

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

# 특정한 합을 가지는 부분 연속 수열 찾기 문제
n = 5 # 데이터 개수
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
  # 현재 start point를 오른쪽으로 옮겼다는 의미
  interval_sum -= data[start]

print(count)

# 정렬되어 있는 두 리스트의 합집합 문제
n, m = 3, 4 # 리스트 A, B 길이
a = [1, 3, 5]
b = [2, 4, 6, 8]

result = [0] * (n + m)
i = 0
j = 0
k = 0

# 모든 원소가 결과 리스트에 담길 때까지
while i < n or j < m:
  # 리스트 B 원소가 모두 처리되었거나, 리스트 A 원소가 더 작을 때
  if j >= m or (i < n and a[i] <= b[j]):
    result[k] = a[i]
    i += 1
  # 리스트 A 원소가 모두 처리되었거나, 리스트 B 원소가 더 작을 때
  else:
    result[k] = b[j]
    j += 1
  k += 1

for i in result:
  print(i, end=' ')

해당 코드는 "이것이 취업을 위한 코딩 테스트다"를 바탕으로 작성했습니다.