투 포인터 기법 (Two Pointers Technique)
쉽게 풀면
정렬된 책장에서 합이 특정 값이 되는 책 두 권의 두께를 찾는다고 해봅시다. 모든 책을 두 권씩 짝지어 하나하나 확인하면 시간이 오래 걸립니다. 대신 한 손가락은 가장 얇은 책에, 다른 손가락은 가장 두꺼운 책에 놓고 시작합니다. 두 책의 두께 합이 목표보다 크면 두꺼운 쪽 손가락을 안쪽으로, 합이 목표보다 작으면 얇은 쪽 손가락을 바깥쪽으로 옮깁니다. 이렇게 두 손가락(포인터)이 서로를 향해 다가가며 후보를 좁혀 나가면, 모든 쌍을 다 확인하지 않고도 훨씬 적은 비교만으로 답을 찾을 수 있습니다.
왜 중요한가
알고리즘 연구와 실무에서는 데이터 크기가 커질수록 이중 반복문(O(n²))의 비용이 급격히 커지기 때문에, 시간 복잡도를 O(n) 수준으로 낮추는 기법은 대규모 데이터 처리 논문에서 성능 개선의 근거로 자주 제시됩니다. 투 포인터 기법은 이러한 선형 시간 최적화의 대표적인 예로, 문자열 매칭, 배열 병합, 네트워크 패킷 스트림 처리 등 다양한 응용 분야에서 기본 구성 요소로 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 데이터를 미리 정렬해 두었기 때문에 두 개의 포인터를 양 끝(또는 같은 방향)에서 움직이는 것만으로 모든 쌍을 확인하는 이중 반복문 없이 답을 찾을 수 있었고, 그 결과 계산 시간이 크게 줄었다는 뜻입니다. 배열·문자열 알고리즘, 데이터 병합 논문에서 흔히 사용됩니다.
서로 다른 두 소스에서 들어오는 정렬된 데이터를 합칠 때, 각 스트림에 포인터 하나씩을 두고 더 작은 값을 차례로 선택해 나가면 별도의 정렬 과정 없이 한 번의 순회만으로 병합할 수 있다는 뜻입니다.
조금 더 깊게 보면
투 포인터 기법은 포인터의 이동 방향에 따라 크게 양 끝에서 시작해 서로를 향해 좁혀가는 방식과, 두 포인터가 같은 방향으로 움직이며 구간을 늘리고 줄이는 방식(슬라이딩 윈도우에 가까운 형태)으로 나뉩니다. 실제 논문에서는 이 기법을 단독으로 쓰기보다 정렬, 해시맵, 이진 탐색 같은 다른 기법과 결합해 특정 조건(예: 중복 제거, 최대 구간 길이)을 만족하는 해를 찾는 데 활용하는 경우가 많으며, 이때 정확성을 증명하기 위해 포인터가 절대 되돌아가지 않는다는 불변식(invariant)을 함께 제시하는 것이 일반적입니다.
주의할 점
투 포인터 기법은 대부분 데이터가 정렬되어 있다는 전제 위에서 동작합니다. 정렬되지 않은 데이터에 그대로 적용하면 포인터를 옮기는 방향을 판단할 기준이 사라져 올바른 답을 보장할 수 없으므로, 필요하다면 먼저 정렬 알고리즘으로 데이터를 정렬한 뒤 적용해야 합니다. 또한 연속된 구간을 유지하며 이동하는 슬라이딩 윈도우 기법과 자주 혼동되는데, 슬라이딩 윈도우가 투 포인터의 한 특수한 활용 형태에 가깝습니다.