Two Pointers (투 포인터)

Two Pointers (투 포인터)

배열이나 리스트에서 두 개의 포인터를 사용하여 조건을 만족하는 구간이나 쌍을 O(N) 시간에 찾는 기법으로, 정렬된 배열이나 연속 구간 문제에 효과적

목적: 선형 시간 탐색, 구간 문제 해결, 쌍 찾기, 부분 배열 문제

특징: 두 포인터 이동, O(N) 시간, 정렬 필요(경우에 따라), 단조성 활용

유형

• •양끝에서 시작: 정렬된 배열에서 합이 특정 값인 쌍 찾기
• •같은 방향: 연속 부분 배열, Sliding Window와 유사
• •서로 다른 배열: 두 배열 병합, 교집합 찾기

대표 문제

• •두 수의 합: 정렬 후 양끝에서 시작, 합에 따라 left++/right--
• •연속 부분 배열 합: left, right 같은 방향, 합에 따라 right++/left++
• •팰린드롬 검사: 양끝에서 시작하여 중앙으로

동작 원리

• •양끝: left=0, right=n-1, 조건에 따라 한쪽 이동
• •같은 방향: left, right 모두 0에서 시작, right 확장 후 left 수축

시간 복잡도: O(N) 또는 O(N log N) (정렬 포함)

공간 복잡도: O(1) (추가 공간 없음)

장점: 선형 시간, 추가 공간 없음, 직관적

단점: 정렬 필요(경우에 따라), 단조성 조건, 문제 유형 제한

적용사례: 두 수의 합, 세 수의 합, 물 채우기, 부분 배열 합

비교: Two Pointers(O(N)/제한적) vs 이분탐색(O(N log N)/범용) vs 해시(O(N)/공간)

연관: 정렬, 이분 탐색, Sliding Window, 구간 문제