[Algorithm] 투 포인터

* Python을 기준으로 합니다

---

투 포인터 (Two Pointer)

- 개념

• 투 포인터 : 배열에서 start, end를 나타내는 포인터를 이동시키면서 값의 위치를 탐색하는 알고리즘
  
  • 배열에서 특정한 합을 가지는 수열이나 중복 값 등을 탐색할 때 사용할 수 있음
    
  • 일반적으로 배열을 순차적으로 탐색하는 데에는 $O(n^{2})$이 소모되지만, 투 포인터를 사용하면 $O(n)$의 time complexity로 해결 가능하기 때문

투 포인터의 동작 예시

- 구현

1. 양 끝에서 시작하는 투 포인터

• 현재 위치에서 일치 여부를 비교한 다음, 포인터를 옮기면서 탐색 범위를 줄이는 방식
  1. 배열의 양 끝에 포인터를 위치시킴
  2. 두 포인터의 합이 작으면 start 포인터를 오른쪽으로 이동, 크면 end 포인터를 왼쪽으로 이동
  3. 정답을 찾을 때까지 위 과정을 반복
     - 이진 탐색과 비슷한 동작 방식

def two_pointer(arr, target):
  result = []
  start = 0
  end = len(arr)-1
  
  arr.sort() #정렬
  while start < end: 
    if arr[start]+arr[end] > target: #기준보다 크면
      end -= 1 #end를 왼쪽으로
    elif arr[start]+arr[end] < target: #기준보다 작으면
      start += 1 #start를 오른쪽으로
    else:
      result.append((arr[start],arr[end]))
      end -= 1
      start += 1
  
  return result

test = [1,9,3,2,4,5,3,7,8,6] 
target = 10
two_pointer(test, target) #[(1, 9), (2, 8), (3, 7), (4, 6)]

2. 한쪽 방향에서 시작하는 투 포인터

• 두 포인터의 시작 위치는 모두 0이지만, 두 포인터의 이동 속도를 다르게 사용
• 구간 만들기 - 배열에서 특정한 합을 가지는 구간을 탐색해야 하는 경우 사용
  1. 두 포인터 모두 0에서 시작
  2. start에서 end 포인터까지의 합이 기준보다 작으면 end 포인터를 이동, 크면 start 포인터를 이동
  3. 정답을 찾을 때까지 위 과정을 반복
     - 결과적으로 한 번의 배열 순회 만으로 탐색이 가능함

def interval_sum(arr, target):
  interval = 0
  end = 0
  count = 0

  #start를 한칸씩 이동
  for start in range(len(arr)):
    while interval < target and end < len(arr): #부분합이 target보다 작으면
      interval += arr[end]
      end += 1 #end 이동
    
    if interval == target: #일치하는 부분합이 있으면
      count += 1 #count 증가
    interval -= arr[start]
  
  return count

test = [1,2,3,4,1]
target = 5
print(interval_sum(test, target)) #2

투 포인터로 구간 합 구하기

• 토끼와 거북이 (Torttoise and Hare) 알고리즘 - 순환 구조 탐색이나 배열의 중복 값 탐색에 사용 
  
  1. 1씩 움직이는 포인터와 2씩 움직이는 포인터를 이동시키면서
  2. 두 포인터가 만나면 cycle이 존재하는 것

def tort_hare(arr):
  hare = tort = arr[0] # 두 포인터 모두 0에서 시작

  while True:
    tort = arr[tort] #1칸씩 이동
    hare = arr[arr[hare]] #2칸씩 이동

    if tort == hare: #만나면
      break
  
  hare = arr[0] #다시 시작점으로 이동시키고
  while hare != tort: #서로 만나면 break하고, 이때 해당 지점이 cycle 발생 지점
    hare = arr[hare] #1칸씩 이동
    tort = arr[tort] #1칸씩 이동

  return hare

#결과 확인
test = [1,9,3,2,4,5,3,7,8,6]
print(tort_hare(test)) #3