개요
아래 내용은 투포인터(two-pointer) 알고리즘의 핵심 개념을 먼저 정리한 뒤, A6투포인터 패키지의 실습 코드(A01TwoPointerBasic.java)를 통해 “문제 정의 → 아이디어 → 구현 흐름 → 시간복잡도 → 확장문제” 순으로 정리한 글이다.
투포인터란?
투포인터는 말 그대로 “두 개의 포인터”를 사용하여 배열이나 리스트를 효율적으로 탐색하는 알고리즘 기법이다.
배열의 양 끝(또는 구간 내 임의의 두 위치)에 포인터를 두고, 조건에 따라 두 포인터를 이동시키면서 원하는 결과를 찾는다.
- 시간복잡도: O(n) (정렬이 필요한 경우 O(n log n))
- 핵심 아이디어:
- 모든 쌍을 완전 탐색하면 O(n²)이지만
- 정렬된 배열에서 두 포인터를 움직이면 한 번의 선형 탐색으로 결과를 얻을 수 있다.
왜 투포인터인가 (브루트포스 비교)
예를 들어, 배열 {7, 8, 9, 2, 4, 5, 1, 3, 6}에서 합이 10이 되는 모든 조합을 찾는다고 하자.
가장 단순한 방법은 다음과 같다.
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == target)
...
}
}- 이 코드의 시간복잡도는 O(n²).
- 원소 수가 커지면 빠르게 비효율적이 된다.
이 문제를 정렬 + 투포인터로 바꾸면 어떤 일이 생길까?
- 정렬된 배열:
[1,2,3,4,5,6,7,8,9] - 두 개의 포인터
start=0,end=n-1을 두고sum = arr[start] + arr[end]를 계산한다.
| sum 비교 | 동작 |
|---|---|
| sum == target | 조합 저장 & start 이동 |
| sum < target | start++ (값을 키워봄) |
| sum > target | end-- (값을 줄여봄) |
이 과정을 거치면 양쪽 포인터가 한 번씩만 움직이므로 선형 탐색으로 끝난다.
실습 1: 두 수의 합 찾기 (A01TwoPointerBasic)
상태 정의 및 초기 조건
- 입력 배열
arr - 목표 값
target - 포인터
start=0, end=arr.length-1
알고리즘 흐름
- 정렬 수행:
Arrays.sort(arr) - 양 끝 포인터 설정:
(start, end) - 조건 비교 및 이동:
sum == target → 조합 저장 → start++sum < target → start++sum > target → end--
코드 중 핵심 부분
while (start < end) {
int sum = arr[start] + arr[end];
if (sum == target) {
twoPointList.add(new int[]{arr[start], arr[end]});
start++;
} else if (sum < target) {
start++;
} else {
end--;
}
}정렬 복잡도 O(n log n)
투포인터 탐색 O(n)
→ 최종적으로 전체 복잡도는 O(n log n) 수준으로 개선된다.
슬라이딩 윈도우와의 차이
| 구분 | 투포인터 | 슬라이딩 윈도우 |
|---|---|---|
| 목적 | 두 포인터의 상대적 거리 조절로 조건 만족하는 구간 찾기 | 고정 길이 윈도우가 이동하면서 구간 상태 계산 |
| 윈도우 크기 | 가변적 | 고정적 |
| 활용 예시 | 두 수의 합, 연속된 합, 최소 구간 | 평균/최댓값 구하기, 로그 분석 |
- 투포인터는 조건 만족 구간을 탐색하는 데 사용.
- 슬라이딩 윈도우는 고정 크기 집합의 상태 변화에 초점.
문제 유형 정리
유형 1) 두 수의 합 / 차
- 정렬 필요
- 포인터 조건:
start < end - 일반적으로 “합/차 특정값 찾기” 형태
유형 2) 구간합 / 수열 범위
- 정렬 불필요
- 포인터 조건:
start <= end - 동일 인덱스부터 확장하며 누적합, 길이, 조건 구간 탐색
정리
투포인터는 정렬 가능한 상황에서 구간을 효율적으로 좁혀가는 탐색 기본기법이다.
탐색 과정이 선형으로 줄어드는 덕분에, 브루트포스보다 월등히 빠르다.
그리고 슬라이딩 윈도우와의 차이를 영리하게 구분하면, “투포인터 계열” 문제(구간합, 부분수열, 투섬, 세섬 등)를 한 흐름에서 이해할 수 있다.
Eazy하게