[AlgorithmTheory] 투포인터(Tow Pointers) 핵심 요약 및 실전 공략법

최근 다시 알고리즘 공부를 하며 다양한 문제를 풀고 있는데 난이도가 올라갈 수록 투포인터와 연계된 문제가 생각보다 많은 듯 하며, 투포인터의 개념은 조금만 공부하면 굉장히 쉽게 느껴져서 필요할 때만 대충 찾아보고 “아 이런거였지” 하며 반복하다 보니 머릿속에 제대로 정리가 안돼서 내용이 남지 않아서 필요할 때마다 개념을 찾아봐야 하는 문제가 있었습니다. 그래서 이번 기회에 투포인터를 한 번 정리 하고 추후에 재학습 때도 본 포스트를 이용하고자 투포인터의 개념에 대한 포스트를 작성하게 되었습니다.

1. 투포인터(Two Pointers)란?

투 포인터는 1차원 배열을 탐색할 때, 두 개의 포인터(인덱스)를 조작하여 원하는 결과를 얻는 알고리즘 기법입니다.

• 투포인터를 사용하는 이유

  이중 반복문을 사용해 완전 탐색을 하면 $O(N^2)$의 시간 복잡도가 발생합니다. 투포인터는 배열의 특정 조건을 활용해 탐색할 필요가 없는 구간을 논리적으로 건너뜀으로써, 시간 복잡도는 $O(N)$으로 압축해 줍니다.

2. 투포인터 문제의 접근 시그널

코딩 테스트에서 다음 두 가지 시그널이 겹친다면, 주저 없이 투포인터를 떠올려야 합니다.

1. 핵심 키워드 시그널

   문제 지문에 다음과 같은 조건이나 단어가 등장할 때 유력합니다.

   • 연속된 부분 배열의 합이 X가 되는…
   • 정렬도니 배열에서 두 수의 합이…
   • 문자열에서 연속된 일부분 중

2. 시간 복잡도 시그널

   • 주어진 배열의 크기 N이 100,000 이상일 때
   • $N=100,000$일 때 $O(N^2)$ 알고리즘을 쓰면 연산량이 100억 번이 되어 무조건 시간 초과(TLE)가 발생합니다. 반드시 $O(N)$ 또는 배열 정렬을 포함한 $O(N \log N)$으로 풀어야 한다는 강력한 힌트입니다.

3. 투포인터 문제의 유형과 유형별 풀이 방법

투포인터는 포인터가 움직이는 방향에 따라 크게 두 가지 유형으로 나뉩니다.

3.1 유형 A: 대립 방향(양 끝 -> 중앙)

양 끝단에 포인터를 배치하고, 서로를 향해 좁혀오는 방식입니다.

항목	핵심내용
전제 조건	배열이 반드시 정렬되어 있어야 함
초기 세팅	left_index = 0, right_index = N-1
이동 논리	현재 합이 목표 보다 크면: right_index -= 1 (값을 줄임) 현재 합이 목표보다 작으면 left_index +=1 (값을 키움)
종료 조건	left_index >= right_index 가 되는 순간 종료 이유: 두 포인터가 만나거나 교차했다는 것은, 이미 배열 내의 모든 가능한 쌍의 탐색을 마쳤음을 의미합니다.
대표 문제	정렬된 배열에서 두 수의 합 찾기, 3Sum, 팰린드롬(회문) 판별

3.2 유형 B: 동일 방향 (시작점 -> 골인)

두 포인터가 모두 인덱스 0에서 출발하여 오른쪽으로 이동하며 구간(Window)를 조절하는 방식입니다.

항목	핵심내용
전제 조건	주로 연속된 구간(부분 배열)을 탐색할 때 사용 (반드시 정렬될 필요는 없음)
초기 세팅	left_index = 0, right_index = 0
이동 논리	-현재 구간 합이 목표보다 작으면: right_index += 1 (구간 확장, 합 증가) - 현재 구간 합이 목표보다 크거나 같으면: left_index += 1 (구간 축소, 합 감소)
종료 조건	right_index == N(배열 끝 도달)이고, 현재 합이 목표값보다 작거나 같을 때 종료 이유: right_index가 끝에 도달하여 더 이상 새로운 원소를 추가할 수 없는데 합이 목표값보다 작거나 같다면, 여기서 left_index를 당겨 구간을 줄여봤자 합ㅂ은 더 작아지기만 하므로 남은 탐색이 무의미
핵심 최적화	O(1) 상태 업데이트: 연속된 구간을 매번 다시 더하지 않고, 이전 합계에서 새로 들어오는 right_index의 값을 더하거나 버려지는 left_index 값을 빼는 연산 수행
대표 문제	연속 부분 배열의 합 찾기, 가장 긴 부분 문자열 구하기

4. 요약 및 마무리

투포인터 문제를 마주했을 때 가져야 할 마인드셋 3줄 요약입니다.

1. 무작정 이중 for문을 돌리기 전에, 정렬이나 연속성을 이용해 불필요한 경우의 수를 버릴 수 있는지 고민해라
2. 매 스텝마다 배열을 다시 훑지 말고, 이전 상태에서 $O(1)$ 연산으로 값만 갱신하라.
3. 두 개의 포인터의 방향이 동일할 경우 데이터에 음수가 있는지 반드시 확인하여 투포인터의 사용 가능 여부를 검증하라.