1. 투포인터란?
•
배열/문자열에서 두 개의 인덱스(포인터)를 이용해
원하는 구간, 쌍, 조건을 빠르게 탐색하는 패턴
•
Brute-force(이중 for문)보다 빠름
(특히 정렬된 배열에서 O(n) ~ O(n log n)으로 최적화 가능)
2. 대표 유형
1) 정렬 + 양끝 포인터 (합/쌍 개수 세기)
•
정렬된 배열에서 left, right 포인터로 탐색
•
조건 만족 시 count += right - left처럼 여러 쌍 한 번에 처리 가능
// 예시: 합이 target 미만인 쌍의 개수 세기
nums.sort((a, b) => a - b);
let left = 0, right = nums.length - 1, count = 0;
while (left < right) {
if (nums[left] + nums[right] < target) {
count += right - left;
left++;
} else {
right--;
}
}
TypeScript
복사
2) 슬라이딩 윈도우 (구간 합/최대길이 등)
•
구간의 시작, 끝 포인터(left, right)를 조절
•
정렬 필요 없음
// 예시: 부분합이 k 이하인 가장 긴 연속 구간
let left = 0, sum = 0, maxLen = 0;
for (let right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum > k) sum -= arr[left++];
maxLen = Math.max(maxLen, right - left + 1);
}
Plain Text
복사
3) 문자열/배열 양끝에서 비교 (팰린드롬 등)
•
주로 left=0, right=n-1에서 가운데로 이동
let left = 0, right = str.length - 1, isPalin = true;
while (left < right) {
if (str[left] !== str[right]) { isPalin = false; break; }
left++; right--;
}
TypeScript
복사
3. 언제, 왜 쓰나?
•
구간, 쌍, 조합 등에서 "불필요한 반복/탐색"을 줄이고 싶을 때
•
정렬된 배열의 특징(단조성, 크기 비교) 덕분에 한 번에 여러 쌍 처리
•
브루트포스(O(n²)) 대신 O(n)~O(n log n)로 속도 개선 가능
4. 주의할 점
•
정렬이 필요한 유형/필요 없는 유형 구분
(쌍 개수 세기는 정렬 필수, 슬라이딩 윈도우는 불필요)
•
(i < j) 쌍 전체가 아닌 "조건 만족하는 쌍"만 빠르게 탐색할 때 사용
5. 정리
"양쪽에서 동시에 이동하며 조건에 맞게 포인터를 조절""정렬 + 양끝, 구간 슬라이딩, 문자열 팰린드롬 등 활용"