📖 1. 개념
: 두 개의 포인터(인덱스)를 사용해서 배열이나 리스트를 효율적으로 탐색하는 알고리즘 기법
[사용 이유]
이중 for문보다 시간 복잡도 측면에서 효율적이기 때문이다.
- 이중 for문 (모든 구간 탐색) :O(n²)
- 투 포인터: O(n) → 각 포인터가 배열을 최대 한 번씩만 순회하기 때문에 총 이동 횟수가 2n이 되기 때문이다.
📎 2. 종류
-
슬라이딩 윈도우
: 같은 방향에서 시작 및 구간을 확장하고 축소한다. (주로 연속된 부분 배열 문제)
-
양 끝 포인터
: 양 끝에서 시작하고 중앙으로 이동한다. (정렬된 배열, 합/차 찾기 문제)
-
빠른-느린 포인터
: 다른 속도로 이동한다. (연결 리스트, 사이클 탐지 문제)
1. 슬라이딩 윈도우 🪟
구간
[left, right]를 유지하면서, right를 확장하고 조건에 따라 left를 축소한다.
L=0
for R in 0..n-1:
상태에 arr[R] 반영 (합/빈도++)
while (제약 위반):
상태에서 arr[L] 제거 (합/빈도--)
L++
최적값 갱신(길이/합 등)let left = 0;
let result = 0; // 또는 최댓값, 최솟값 등
for (let right = 0; right < n; right++) {
// 1. right 위치 요소를 윈도우에 추가
window에 arr[right] 추가;
// 2. 조건 위반 시 left를 이동하여 조정
while (조건 위반) {
window에서 arr[left] 제거;
left++;
}
// 3. 현재 윈도우로 결과 갱신
result = 갱신(result, right - left + 1);
}ex: 백준 30804번(조건을 만족하는 최대 연속 구간 길이 구하기), 1806번(연속된 수들의 합이 M이상이 되는 최소 길이) etc…
2. 양 끝 포인터 🔚
배열의 양 끝에서 시작해서 중앙으로 이동하면서 탐색한다.
L=0, R=n-1
while (L < R):
if sum(L,R) == target: 정답/기록
if sum(L,R) < target: L++ // 더 키우기
else: R-- // 더 줄이기let left = 0;
let right = n - 1;
while (left < right) {
if (조건 만족) {
// 답 찾음
break;
} else if (값을 키워야 함) {
left++;
} else {
right--;
}
}예제: 백준 3273번(정렬된 배열에서 합이 X인 서로 다른 두 수 찾기), 2143번(정렬된 배열에서 합이 0에 가장 가까운 세 수 찾기), 팰린드롬 판별
3. 빠른-느린 포인터 🐇🐢
서로 다른 속도로 이동하는 두 포인터 사용한다.
예제: 연결 리스트 사이클 탐지 (Floyd's Algorithm), 연결 리스트 중간 노드 찾기, 배열에서 중복 제거 (in-place), 백준 2018번(N을 연속된 자연수의 합으로 나타내는 경우의 수)
👩⚖️ 3. 투포인터 문제 판별법
- "연속된 부분 배열/문자열"
- 최대/최소 길이
- 특정 조건을 만족하는 구간
- "정렬된 배열"에서 합/차 찾기
- 두 수의 합
- 세 수의 합
- "O(n²)를 O(n)으로 개선"
- 이중 for문을 사용할 것 같은데 시간 제한이 빡빡함
- "연결 리스트" 관련
- 중간 찾기
- 사이클 탐지
예제:
- 백준 2003: 수들의 합 2
- 백준 1940: 주몽
- 백준 2018: 수들의 합 5
- 백준 30804: 과일 탕후루
- 백준 3273: 두 수의 합
- 백준 1806: 부분합
- 백준 2230: 수 고르기
- 백준 1644: 소수의 연속합
- 백준 2531: 회전 초밥
- 백준 2143: 두 배열의 합
- 백준 1450: 냅색문제
- 백준 7453: 합이 0인 네 정수
출처:
밝은 미래 FE 개발자의 기록