투포인터

투포인터의 정의 및 장단점

 

• Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘
• 여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다.
• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.
• 투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다.
• 보통 lt(left), rt(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다.

 

 

 

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

투포인터 알고리즘의 대표적인 문제입니다.

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제입니다.

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트한다.
3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

위와 같은 리스트와 M=5M=5 일 때의 예시를 생각해봅시다.

• [초기 단계] : 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 합니다.

  • 

  • 현재의 부분 합은 1.
  • 현재 카운트 : 0
• [Step 1] : 이전 단계에서의 부분합이 1 -> end를 증가시킵니다.

  • 

  • 현재의 부분 합 : 3
  • 현재 카운트 : 0
• [Step 2] : 부분합이 3 -> end를 증가시킵니다.

  • 

  • 현재의 부분 합 : 6
  • 현재 카운트 : 0
• [Step 3] : 부분합 6 -> start를 1 증가시킵니다.

  • 

  • 현재의 부분 합 : 5
  • 현재 카운트 : 1 (부분합이 5이기 때문에)
• 이걸 계속 반복하다가 마지막
• [마지막]

  • 

  • 현재의 부분합 : 5

코드

n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M

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)

시간복잡도

O(N)

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝납니다. -> 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)입니다