투 포인터

흔히 투 포인터라고 부르기는 하는데, 정확히 뭐를 투 포인터라고 부르는지 명확하게 정의된건 아닌것 같다. 대충, 두 개의 포인터를 유지하면서 조건에 따라서 적합한 한쪽을 이동시키는 것을 반복하는 방식으로 작동하는 알고리즘이면 전부 다 투 포인터로 부를 수 있는거 같긴 하다. 일반적으로는 한개의 일차원 배열 상에서, 양쪽 끝에서 출발하는 포인터 두개를 갖고 작업하거나, 한쪽에서 출발하는 두개의 포인터를 갖고 작업하는 경우에 쓰이는것 같지만, 두개의 정렬된 배열에 대해서 두개의 포인터를 유지하면서 머지하는 것을 구현하는 문제에도 투 포인터라는 태그가 붙어있는 것을 보기도 했다.

대표적인 활용방법은, 주어진 수들 중에서 합이 X에 가까운 두 수를 찾을때, 또는 차가 X에 가까운 찾을때 사용하는 것이다. 주어진 수들을 정렬하고, 합이 X에 가까운 수를 찾을때는 두개의 포인터가 양쪽 끝(최소값과 최대값)에서 출발하고, 차가 X에 가까운 수를 찾을때는 두개의 포인터가 한쪽 끝에서 출발하게 된다.

다른 흔한 유형인, 합이 X에 가깝게 되는 부분배열을 찾는 문제는 여기에 해당이 안되는거 같아 보이기도 하는데 결국은 같은 유형이다. sum(a[i:j] 가)가 X가 되는 i,j를 찾는 것인데, 누적합 배열로 바꿔서 생각하면, p[k] = sum(a[:k]) 인 누적합 배열은 정렬된 상태이고, sum(a[i:j]) = sum(a[:j]) - sum(a[:i]) 이므로 결국 누적합 배열에서 차가 X가 되는 i,j를 찾는 문제이다. 따라서 한쪽 끝에서 두개의 포인터가 출발하게 된다.

보통 c++ 로 짠다면, l과 r이 두개의 인덱스를 저장하고 있고, while 루프 안에서 조건에 따라서 l또는 r이 갱신되는 방식으로 구현할 것이다. 또는 인덱스 대신 포인터를 저장하는 식으로 짤 수도 있을것이다. 아무튼 이게 직관적이다

하지만 python에서는 배열을 인덱스로 접근하는 것이 효율성에서 좋지 못하다. 그러다보니 다른 방식을 시도하게 되는데, 예를 들면 한쪽포인터를 움직이는 것을 for 루프로 잡고, 그 안에서 다른쪽 포인터를 움직이는 while루프를 만드는 것이다. 파이썬 특성에 따르면 이게 좀더 효율적이기는 할텐데, 문제는 알고리즘이 한눈에 바로 들어오지 않는다는 것이다

우선 배열의 인덱스 접근을 피하는 방법은, iterator를 만들어서 next()로 움직이는 방법이 있다. 이 방법은 보기에도 깔끔하다. 이 방법을 사용하자.

그다음에.. while True 루프 안에서 l또는 r을 움직일것인가, 이중 루프를 쓸것인가인데.. 우선 코드 예시를 들어보자. 합이 N인 부분수열의 갯수를 구하는 코드이다

while True:
  try:
    if num_sum == N:
      answer += 1
    if num_sum <= N:
      num_sum += next(right_iter)
    else:
      num_sum -= next(left_iter)
  except StopIteration:
    break

for num in right_iter:
  num_sum += num 
  while num_sum > N:
    num_sum -= next(left_iter)
  if num_sum == N:
    answer += 1

전자가 코드가 좀더 길긴 하지만, 대칭적이라서 좀더 알아보기 쉬운 느낌이다. 전자의 형식으로 코딩하는걸로 결정..

(TODO) 생각해보니.. 리스트와 두개의 인덱스 또는 두개의 이터레이터를 갖고 다니는 방법 대신에 그냥 데이터를 deque에 저장하고 양쪽에서 pop해버리면서 처리하는것도 가능할것 같다. 코드는 더 깔끔해질거 같은데 속도가 얼마나 떨어지려나.. 한번 테스트해보자.

주로 투 포인터를 사용해서 푸는 문제들이지만, 투 포인터가 아닌 방법으로도 풀리는 문제들도 많다

정렬 후 투포인터로 풀 수 있다. O(nlogn) + O(n) = O(nlogn)

하지만, 그냥 딕셔너리(카운터)에 모든 수와 등장 횟수를 저장하고, 모든 a[i]에 대해서 값이 X-a[i]인 원소의 수를 찾아서 합치면 정렬 없이 O(n)에 풀린다. 이 방식을 쓰자.

두 수의 차가 X가 되는 쌍의 경우도 동일하다.

정렬 후 투 포인터로 푼다. 한쪽끝에서 두개의 포인터를 출발시킨다. O(nlogn) + O(n) = O(nlogn)

차가 X인 쌍을 구하는 것과 마찬가지로 정렬 후 투 포인터로 풀 수 있다. 양쪽 끝에서 포인터들을 출발시킨다. O(nlogn) + O(n) = O(nlogn)

맨 처음에 말했듯이, 누적합 배열을 만든 뒤에 차가 X에 가깝게 되는 두 수를 찾아도 풀이가 가능하지만, 그냥 누적합 배열을 안만들고 원래 배열에서 바로 투포인터를 돌리는 것이 간단하다.

슬라이딩 윈도우는 모든 부분구간들에 대해서 처리할때 사용되는 기법이다. 고정된 사이즈의 윈도우를 이동시키면 그 안에 포함되는 부분구간들을 처리한다는 느낌으로 붙인 이름인데. 사실상 투 포인터에서 두개의 포인터가 일정한 간격을 두고서 움직이는 것과 동일하다.