투 포인터(Two Pointers)

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

말 그대로 두 개의 포인터(인덱스)를 사용하여 배열이나 리스트를 효과적으로 탐색하는 기법이다.

• O(N)의 시간 복잡도를 가짐

 

2. 주요 유형

 

2.1. 시작점과 끝점에서 만나는 방식(양끝 조합)

주로 정렬된 배열에서 두 수의 합이 특정 K와 일치하는지 찾을 때 사용된다.

• Pointer 1 (Left): 배열의 시작점에서 오른쪽으로 이동한다.
• Pointer 2 (Right): 배열의 시작점에서 왼쪽으로 이동한다.
• 동작: 포인터에 위치한 두 요소의 합이 K보다 작으면 Left++, 크면 Right-- 를 수행하며 포인터를 이동한다.

 

2.2. 같은 방향으로 진행하는 방식(슬라이딩 윈도우)

연속된 부분 수열의 합이 특정 값 K를 만족하는지 찾을 때 사용된다. 배열의 정렬이 필요하지 않다.

• Start: 부분 구간의 시작
• End: 부분 구간의 끝
• 동작: 구간의 합이 타겟 K 보다 작으면 End를 키워 구간을 늘리고, 타겟 K 보다 크면 Start를 키워 구간을 줄인다.

 

 

3. 사용 시나리오

상황	해결 방법
배열에서 두 수의 합 찾기	1. 배열 정렬 2. 양 끝에서 포인터를 좁혀가며 탐색한다.
특정 합을 가지는 부분 연속 수열 찾기	start, end를 인덱스 0에서 시작하여 조건에 따라 늘리고 줄이며 배열 끝까지 탐색한다.
정렬된 두 배열 합치기	각 배열의 시작점에 포인터를 두고 작은 값을 먼저 결과에 담는다.

 

 

 

4. 알고리즘 설계 팁

• 포인터의 초기 위치: (0, 0)에서 시작할 것인지, 아니면 (0, N-1)에서 시작할 것인지
• 포인터 이동 조건: 어떤 상황에서 왼쪽 혹은 오른쪽 포인터를 움직일 것인지
• 반복 종료 조건: 두 포인터가 겹치면 끝낼 것인지, 배열의 끝에 도달하면 끝낼 것인지
• 주의: 투 포인터를 적용하기 전에 배열이 정렬되어야하는지 확인한다. 합을 찾는 문제에는 정렬이 필수일 경우가 많다.