투 포인터(Two Pointers Algorithm)

 

투 포인터란?

정렬된 배열에서 한 쌍씩 검색하는데 사용되는 쉽고 효과적인 알고리즘이다.

두개의 기준을 잡고 안에 값들에 다라 조건을 걸어, 두 기준(pointer) 들을 옮겨주는 양상이다. 

정렬된 배열 A(오름차순으로 정렬됨)가 N개의 정수를 가지고,

그 합이 X와 같도록 원소 쌍(A[i], A[j])이 존재하는지 알아보고자 하는 상황에서 투 포인터를 사용할 수 있다. 

 

def isPairSum(A, N, X):
  
    for i in range(N):
        for j in range(N):
  
            if(i == j):
                continue
  
            if (A[i] + A[j] == X):
                return True
  
            if (A[i] + A[j] > X):
                break
    return 0

  
arr = [2, 3, 5, 8, 9, 10, 11]
val = 17
  
print(isPairSum(arr, len(arr), val))

---

A[] = {10, 20, 35, 50, 75, 80}
X == 70
i = 0
j = 5

---

A[i] + A[j] = 10 + 80 = 90
A[i] + A[j] > X

j-- 이후
i = 0
j = 4

---

A[i] + A[j] = 10 + 75 = 85
A[i] + A[j] > X

 j-- 이후
i = 0
j = 3

---

A[i] + A[j] = 10 + 50 = 60
A[i] + A[j] < X

i++ 이후
i = 1
j = 3

---

A[i] + A[j] = 20 + 50 = 70

따라서 쌍이 발견되었다.

다음과 같은 두 포인터 알고리즘의 작동에 대해 간략히 논의해보자

투포인터 알고리즘은 기본적으로 입력 배열이 정렬되어 있다는 가정하에 사용한다.

우리는 극단값의 합(최소값과 최대값)을 시작하고 두 포인터를 조건부로 이동시킨다.

A[i]와 A[j]의 합이 X보다 작을 때 왼쪽 포인터 'i'를 이동한다. 합계가 이미 X보다 작기 때문에 우리는 어떤 쌍도 놓치지 않는다. 오른쪽 포인터 j에도 같은 논리가 적용된다.

 

논리적으로 말 했을 떄 이해가 되지 않을 수도 있다. 그림을 통해 이해해보자 

 

이제는 백준 문제로 느낌을 이해해보자 

1806번: 부분합

 

주어진 배열에서 부분합중 S이상 이지만 길이가 가장 짧은 부분합의 길이를 출력해야한다. 

right와 left를 0으로 두고 tmp_sum이 S보다 클 경우 right를 오른쪽으로 옮기며 ,

S보다 작을 경우 left를 오른쪽으로 옮긴다. 

이렇게 계소해서 움직이다가 결국 right의 인덱스가 끝을 도달하면 break한다. 

 

import sys
input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))

left, right = 0, 0
tmp_sum = 0
min_length = sys.maxsize

while True:
   if tmp_sum >= S:
       min_length = min(min_length, right - left)
       tmp_sum -= arr[left]
       left += 1

   elif right == N:
       break

   else:
       tmp_sum += arr[right]
       right += 1

if min_length == sys.maxsize:
   print(0)
else:
   print(min_length)

 

이미지 참고)https://towardsdatascience.com/two-pointer-approach-python-code-f3986b602640