명이나물 라이브러리View
투포인터 알고리즘
1. 투포인터란?
투포인터는 배열이나 리스트에서 두 개의 인덱스, 즉 포인터를 사용해 원하는 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법이다.
보통 left, right 또는 start, end라는 이름의 변수를 사용한다.
예를 들어 배열이 다음과 같이 있을 때,
int[] arr = {1, 2, 3, 4, 5};두 개의 포인터를 사용해 특정 구간을 살펴보거나, 두 수의 합을 비교할 수 있다.
[1, 2, 3, 4, 5]
L R여기서 L은 왼쪽 포인터, R은 오른쪽 포인터다.
2. 투포인터를 사용하는 이유
배열에서 두 수를 고르거나, 연속된 구간의 합을 구하는 문제를 단순하게 풀면 보통 이중 반복문을 사용하게 된다.
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// 모든 조합 확인
}
}이 방식의 시간복잡도는 O(N²)이다.
배열의 길이가 작다면 괜찮지만, 입력 크기가 커지면 시간초과가 발생할 수 있다.
투포인터를 사용하면 불필요한 탐색을 줄여서 보통 O(N) 또는 정렬이 필요한 경우 O(N log N)에 문제를 해결할 수 있다.
즉, 투포인터의 핵심은 다음과 같다.
모든 경우를 다 확인하지 않고,
조건에 따라 포인터를 이동하면서 정답 후보만 효율적으로 탐색한다.3. 투포인터의 대표 유형
투포인터는 크게 두 가지 유형으로 자주 등장한다.
| 유형 | 포인터 이동 방식 | 대표 문제 |
|---|---|---|
| 양끝에서 좁히기 | left →, right ← |
정렬 배열에서 두 수의 합 찾기 |
| 같은 방향으로 이동하기 | start →, end → |
연속 부분합, 구간 길이 문제 |
유형 1. 양끝에서 좁히는 투포인터
4. 정렬된 배열에서 두 수의 합 찾기
가장 대표적인 투포인터 문제는 정렬된 배열에서 두 수의 합이 target이 되는지 찾는 문제다.
예를 들어 다음 배열이 있다고 하자.
int[] arr = {1, 2, 3, 4, 6};
int target = 6;이 배열에서 합이 6이 되는 두 수는 2와 4다.
단순하게 모든 쌍을 비교하면 O(N²)이지만, 배열이 정렬되어 있다면 투포인터로 더 빠르게 찾을 수 있다.
5. 동작 방식
처음에는 left를 배열의 맨 앞에, right를 배열의 맨 뒤에 둔다.
arr = [1, 2, 3, 4, 6]
L R현재 합은 다음과 같다.
arr[left] + arr[right] = 1 + 6 = 77은 target인 6보다 크다.
배열이 오름차순으로 정렬되어 있기 때문에, 합을 줄이려면 더 큰 값을 가리키는 right를 왼쪽으로 이동하면 된다.
arr = [1, 2, 3, 4, 6]
L R이제 합은 다음과 같다.
1 + 4 = 5이번에는 target보다 작다.
합을 키워야 하므로 left를 오른쪽으로 이동한다.
arr = [1, 2, 3, 4, 6]
L R이제 합은 다음과 같다.
2 + 4 = 6정답을 찾았다.
6. 왜 합이 크면 right를 줄일까?
정렬된 배열에서는 오른쪽으로 갈수록 값이 커진다.
[1, 2, 3, 4, 6]
작은 값 큰 값현재 합이 너무 크다면, 큰 값을 줄여야 한다.
따라서 오른쪽에 있는 right를 왼쪽으로 이동한다.
반대로 현재 합이 너무 작다면, 작은 값을 키워야 한다.
따라서 왼쪽에 있는 left를 오른쪽으로 이동한다.
정리하면 다음과 같다.
| 현재 합 | 이동할 포인터 | 이유 |
|---|---|---|
sum < target |
left++ |
더 큰 값을 선택해서 합을 키움 |
sum > target |
right-- |
더 작은 값을 선택해서 합을 줄임 |
sum == target |
정답 | 조건 만족 |
7. Java 코드
class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 6};
int target = 6;
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println(arr[left] + " + " + arr[right] + " = " + target);
return;
}
if (sum < target) {
left++;
} else {
right--;
}
}
System.out.println("조건을 만족하는 두 수가 없습니다.");
}
}유형 2. 같은 방향으로 이동하는 투포인터
8. 연속 부분합 문제
두 번째 대표 유형은 연속된 구간의 합을 구하는 문제다.
예를 들어 다음 배열에서 합이 5가 되는 연속 구간의 개수를 구한다고 하자.
int[] arr = {1, 2, 3, 2, 5};
int target = 5;가능한 구간은 다음과 같다.
[2, 3]
[3, 2]
[5]정답은 3개다.
이 문제에서는 start, end 두 포인터를 사용한다.
[start, end]또는 코드 구현에 따라 [start, end) 형태로 관리하기도 한다.
9. 연속 부분합에서 포인터의 역할
연속 부분합 문제에서는 보통 두 포인터가 같은 방향으로 이동한다.
start →
end →
[1, 2, 3, 2, 5]각 포인터의 역할은 다음과 같다.
| 포인터 | 역할 |
|---|---|
end 또는 right |
구간을 오른쪽으로 확장 |
start 또는 left |
구간의 왼쪽을 줄임 |
sum |
현재 구간의 합 |
현재 합이 target보다 작으면 구간을 키워야 한다.
sum += arr[right];
right++;현재 합이 target보다 크면 구간을 줄여야 한다.
sum -= arr[left];
left++;10. Java 코드
class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 5};
int target = 5;
int left = 0;
int sum = 0;
int count = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum > target) {
sum -= arr[left];
left++;
}
if (sum == target) {
count++;
}
}
System.out.println(count);
}
}11. 이 코드가 가능한 이유
위 방식은 배열의 원소가 모두 양수일 때 잘 동작한다.
원소가 모두 양수라면 다음이 성립한다.
right를 이동해서 값을 추가하면 sum은 증가한다.
left를 이동해서 값을 제거하면 sum은 감소한다.그래서 현재 합에 따라 포인터를 이동할 수 있다.
sum < target → right 이동
sum > target → left 이동
sum == target → 정답 처리하지만 배열에 음수가 포함되어 있다면 이야기가 달라진다.
예를 들어 음수가 있으면 오른쪽 값을 추가했는데 오히려 합이 줄어들 수도 있다.
이 경우 단순 투포인터가 깨질 수 있고, 누적합이나 HashMap 같은 다른 접근이 필요할 수 있다.
12. 투포인터와 슬라이딩 윈도우 차이
투포인터와 슬라이딩 윈도우는 비슷하게 보인다.
둘 다 구간을 다루고, left, right를 사용한다.
하지만 차이가 있다.
| 구분 | 투포인터 | 슬라이딩 윈도우 |
|---|---|---|
| 구간 길이 | 보통 가변 길이 | 보통 고정 길이 |
| 대표 문제 | 합이 target인 구간 찾기 | 길이 K 구간의 최대합 |
| 이동 방식 | 조건에 따라 한쪽 또는 양쪽 이동 | 일정 크기의 창을 유지하며 이동 |
예를 들어 길이가 3인 연속 구간의 최대 합을 구하는 문제는 슬라이딩 윈도우에 가깝다.
[1, 2, 3], 2, 5
1, [2, 3, 2], 5
1, 2, [3, 2, 5]반면, 합이 target이 되는 구간을 찾는 문제는 투포인터에 가깝다.
13. 투포인터를 사용할 수 있는 조건
투포인터는 아무 문제에나 사용할 수 있는 것은 아니다.
중요한 조건은 다음과 같다.
13-1. 포인터를 이동했을 때 결과 변화를 예측할 수 있어야 한다
예를 들어 정렬된 배열에서 두 수의 합을 찾는 문제에서는 다음 판단이 가능하다.
sum < target → left를 오른쪽으로 이동하면 합이 커짐
sum > target → right를 왼쪽으로 이동하면 합이 작아짐이 판단이 가능하기 때문에 투포인터를 사용할 수 있다.
13-2. 연속 구간 문제에서는 원소가 양수인 경우가 많다
연속 부분합 문제에서는 원소가 모두 양수라면 다음이 가능하다.
right 이동 → sum 증가
left 이동 → sum 감소그래서 현재 합을 기준으로 구간을 늘리거나 줄일 수 있다.
13-3. 한 번 지나간 값을 다시 볼 필요가 없어야 한다
투포인터의 장점은 각 포인터가 한 방향으로만 이동한다는 점이다.
left → → →
right → → →또는
left → → →
right ← ← ←이렇게 움직이면 각 원소를 여러 번 반복해서 확인하지 않아도 된다.
14. 시간복잡도
투포인터는 보통 O(N)이다.
겉으로 보면 반복문 안에 또 다른 반복문이 있는 경우도 있다.
for (int right = 0; right < arr.length; right++) {
while (sum > target) {
left++;
}
}하지만 left와 right는 각각 배열을 한 번씩만 지나간다.
right: 최대 N번 이동
left : 최대 N번 이동따라서 전체 이동 횟수는 대략 2N이고, 빅오 표기법으로는 O(N)이다.
정렬이 필요한 문제라면 정렬 비용이 추가된다.
정렬 O(N log N) + 투포인터 O(N)
= O(N log N)15. 자주 나오는 투포인터 문제 유형
코딩테스트에서 투포인터는 다음과 같은 문제에서 자주 등장한다.
| 문제 유형 | 설명 |
|---|---|
| 두 수의 합 | 정렬된 배열에서 합이 target인 두 수 찾기 |
| 세 수의 합 | 정렬 후 하나를 고정하고 나머지를 투포인터로 탐색 |
| 연속 부분합 | 합이 target인 연속 구간 찾기 |
| 가장 짧은 구간 | 조건을 만족하는 최소 길이 구간 찾기 |
| 중복 제거 | 정렬 배열에서 중복 없이 정리 |
| 팰린드롬 검사 | 양끝 문자를 비교하며 안쪽으로 이동 |
| 0에 가까운 두 수 | 정렬 배열에서 합의 절댓값 최소 찾기 |
16. 투포인터 기본 템플릿
16-1. 양끝에서 좁히기 템플릿
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
// 정답 처리
} else if (sum < target) {
left++;
} else {
right--;
}
}이 템플릿은 정렬된 배열에서 두 수의 합을 찾을 때 자주 사용한다.
16-2. 같은 방향으로 이동하는 템플릿
int left = 0;
int sum = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum > target) {
sum -= arr[left];
left++;
}
if (sum == target) {
// 정답 처리
}
}이 템플릿은 연속 부분합 문제에서 자주 사용한다.
17. 주의할 점
17-1. =+와 +=는 다르다
투포인터 문제를 풀 때 sum을 갱신하는 경우가 많다.
이때 아래처럼 쓰면 안 된다.
sum =+ arr[right];이 코드는 sum += arr[right]와 다르다.
올바른 코드는 다음과 같다.
sum += arr[right];빼기도 마찬가지다.
sum -= arr[left];17-2. 포인터 이동 순서를 조심해야 한다
아래 코드는 현재 값을 건너뛸 수 있다.
sum += arr[++right];++right는 먼저 증가한 뒤 배열에 접근한다.
처음 투포인터를 연습할 때는 아래처럼 분리해서 쓰는 것이 안전하다.
sum += arr[right];
right++;또는 for문으로 right를 관리하는 방식이 더 깔끔할 수 있다.
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
}
18. 최종 정리
투포인터는 두 개의 포인터를 사용해 불필요한 탐색을 줄이는 알고리즘 기법이다.
핵심은 다음과 같다.
1. 두 개의 포인터를 둔다.
2. 현재 조건을 확인한다.
3. 조건에 따라 한쪽 포인터를 이동한다.
4. 정답 후보를 갱신한다.투포인터를 사용할 때 가장 중요한 것은 포인터의 역할을 명확히 정하는 것이다.
left는 무엇을 의미하는가?
right는 무엇을 의미하는가?
sum은 어떤 구간의 합인가?
포인터를 이동하면 값이 어떻게 변하는가?이 질문에 답할 수 있다면 투포인터 문제를 훨씬 쉽게 풀 수 있다.
정리하면 다음과 같다.
| 상황 | 이동 방식 |
|---|---|
| 정렬 배열에서 두 수의 합 | 양끝에서 좁히기 |
| 연속 부분합 | 같은 방향으로 이동하기 |
| 합이 작을 때 | 보통 구간 확장 |
| 합이 클 때 | 보통 구간 축소 |
투포인터는 처음에는 헷갈릴 수 있지만, 한 번 감을 잡으면 코딩테스트에서 매우 자주 활용할 수 있는 강력한 기법이다.