[알고리즘] 36. 투 포인터
지난 글에서는 Comparator를 이용해 원하는 기준으로 정렬하는 방법을 정리했습니다. 이번 글에서는 정렬된 배열이나 연속 구간 문제에서 자주 사용하는 투 포인터(Two Pointers)에 대해 알아보겠습니다.
투 포인터는 이름 그대로 두 개의 포인터를 사용해서 문제를 해결하는 방법입니다. 배열이나 리스트에서 두 위치를 가리키는 변수를 두고, 조건에 따라 한쪽 또는 양쪽 포인터를 움직입니다.
투 포인터는 두 개의 위치 변수를 움직이며 조건을 만족하는 값을 찾는 알고리즘 기법입니다.
1. 투 포인터란?
투 포인터는 배열에서 두 개의 인덱스를 사용해 탐색 범위를 조절하는 방식입니다. 보통 left와 right, 또는 start와 end라는 이름을 사용합니다.
배열: [1, 2, 3, 4, 5]
left → 첫 번째 위치
right → 마지막 위치두 포인터가 가리키는 값을 비교하거나 합을 계산하면서 조건에 따라 포인터를 움직입니다.
합이 작으면 left를 오른쪽으로 이동
합이 크면 right를 왼쪽으로 이동이처럼 불필요한 탐색을 줄이면서 효율적으로 답을 찾는 것이 투 포인터의 핵심입니다.
투 포인터는 두 위치를 동시에 관리하면서 탐색 범위를 줄이는 방법입니다.
2. 투 포인터가 필요한 이유
배열에서 두 수의 합을 찾는 문제를 생각해보겠습니다. 가장 단순한 방법은 모든 두 수의 조합을 확인하는 것입니다.
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == target) {
System.out.println("찾음");
}
}
}이 방식은 이중 반복문을 사용하므로 시간복잡도가 O(N²)입니다. N이 작다면 괜찮지만, N이 커지면 시간 초과가 발생할 수 있습니다.
하지만 배열이 정렬되어 있다면 투 포인터를 이용해 훨씬 효율적으로 해결할 수 있습니다. 두 포인터를 양쪽 끝에 두고 합을 비교하면서 이동하면 됩니다.
투 포인터는 이중 반복문을 줄여 O(N)으로 해결할 수 있는 경우가 많습니다.
3. 투 포인터의 대표 형태
투 포인터는 크게 두 가지 형태로 자주 사용됩니다.
| 형태 | 설명 | 대표 문제 |
|---|---|---|
| 양쪽 끝에서 좁히기 | left는 앞에서, right는 뒤에서 시작 | 두 수의 합, 정렬 배열 탐색 |
| 같은 방향으로 이동 | start와 end가 둘 다 오른쪽으로 이동 | 연속 부분합, 구간 합 |
이번 글에서는 먼저 가장 기본적인 형태인 양쪽 끝에서 좁히는 투 포인터를 중심으로 보겠습니다. 같은 방향으로 이동하는 방식은 다음 글의 슬라이딩 윈도우와도 연결됩니다.
4. 정렬된 배열에서 두 수의 합 찾기
정렬된 배열에서 두 수를 골라 합이 target이 되는지 확인해보겠습니다.
배열: [1, 2, 3, 4, 5, 6]
target = 9처음에는 left를 가장 왼쪽, right를 가장 오른쪽에 둡니다.
left = 0 → 값 1
right = 5 → 값 6
합 = 1 + 6 = 7합이 9보다 작습니다. 합을 더 크게 만들려면 작은 쪽 값인 left를 오른쪽으로 옮겨야 합니다.
left 이동
2 + 6 = 8
left 이동
3 + 6 = 9 → 찾음정렬되어 있기 때문에 합이 작을 때는 left를 움직이고, 합이 클 때는 right를 움직일 수 있습니다.
5. 두 수의 합 Java 코드
정렬된 배열에서 두 수의 합이 target이 되는지 확인하는 코드는 다음과 같습니다.
int[] arr = {1, 2, 3, 4, 5, 6};
int target = 9;
int left = 0;
int right = arr.length - 1;
boolean found = false;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
found = true;
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
System.out.println(found);출력 결과는 다음과 같습니다.
true3과 6의 합이 9이므로 true가 출력됩니다.
정렬된 배열에서 두 수의 합을 찾을 때 투 포인터를 자주 사용합니다.
6. 포인터 이동 기준
투 포인터에서 가장 중요한 것은 포인터를 어떤 기준으로 움직일지 정하는 것입니다. 두 수의 합 문제에서는 다음 기준을 사용합니다.
| 현재 합 | 이동 | 이유 |
|---|---|---|
| sum == target | 정답 발견 | 원하는 합을 찾음 |
| sum < target | left++ | 합을 더 크게 만들어야 함 |
| sum > target | right-- | 합을 더 작게 만들어야 함 |
이 기준이 성립하려면 배열이 정렬되어 있어야 합니다. 정렬되어 있어야 left를 오른쪽으로 옮겼을 때 값이 커지고, right를 왼쪽으로 옮겼을 때 값이 작아진다고 판단할 수 있습니다.
투 포인터의 이동 기준은 정렬 상태를 이용해 결정합니다.
7. 정렬되지 않은 배열이라면?
투 포인터를 사용하려면 보통 배열이 정렬되어 있어야 합니다. 정렬되지 않은 배열에서는 left와 right를 움직였을 때 합이 커질지 작아질지 예측할 수 없습니다.
정렬되지 않은 배열: [4, 1, 6, 2, 5, 3]이 배열에서는 left를 오른쪽으로 옮긴다고 해서 값이 커진다고 보장할 수 없습니다. 따라서 투 포인터를 사용하기 전에 정렬이 필요한지 확인해야 합니다.
Arrays.sort(arr);다만 정렬하면 원래 인덱스 정보가 바뀝니다. 문제에서 원래 위치가 필요하다면 값과 인덱스를 함께 저장하는 방식이 필요할 수 있습니다.
8. 두 수의 합 개수 세기
이번에는 두 수의 합이 target이 되는 경우의 개수를 세어보겠습니다. 중복이 없는 정렬 배열이라고 가정합니다.
배열: [1, 2, 3, 4, 5, 6]
target = 7
가능한 쌍:
1 + 6
2 + 5
3 + 4코드는 다음과 같습니다.
int[] arr = {1, 2, 3, 4, 5, 6};
int target = 7;
int left = 0;
int right = arr.length - 1;
int count = 0;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
count++;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
System.out.println(count);출력 결과는 다음과 같습니다.
3합이 target인 쌍을 찾으면 양쪽 포인터를 모두 이동시켜 다음 후보를 확인합니다.
9. 가장 작은 차이 찾기
투 포인터는 두 값의 차이를 조절하는 문제에도 사용할 수 있습니다. 예를 들어 정렬된 배열에서 target에 가장 가까운 두 수의 합을 찾는 문제를 생각해볼 수 있습니다.
기본 아이디어는 현재 합과 target의 차이를 계속 비교하면서 더 가까운 값을 저장하는 것입니다.
int[] arr = {1, 3, 4, 7, 10};
int target = 12;
int left = 0;
int right = arr.length - 1;
int bestSum = arr[left] + arr[right];
int minDiff = Math.abs(bestSum - target);
while (left < right) {
int sum = arr[left] + arr[right];
int diff = Math.abs(sum - target);
if (diff < minDiff) {
minDiff = diff;
bestSum = sum;
}
if (sum < target) {
left++;
} else {
right--;
}
}
System.out.println(bestSum);현재 합이 target보다 작으면 합을 키우기 위해 left를 이동하고, target보다 크면 합을 줄이기 위해 right를 이동합니다.
10. 양쪽 끝에서 좁히는 투 포인터 패턴
양쪽 끝에서 좁히는 투 포인터의 기본 형태는 다음과 같습니다.
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
// 정답 처리
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}이 패턴은 정렬된 배열에서 두 값을 골라 조건을 만족시키는 문제에 자주 사용됩니다.
양쪽 투 포인터는 left가 오른쪽으로, right가 왼쪽으로 이동하며 범위를 좁힙니다.
11. 같은 방향으로 움직이는 투 포인터
투 포인터는 양쪽 끝에서만 사용하는 것이 아닙니다. 두 포인터가 같은 방향으로 움직이는 형태도 있습니다. 대표적으로 연속 부분합 문제가 있습니다.
배열: [1, 2, 3, 2, 5]
target = 5
연속 구간:
2 + 3 = 5
3 + 2 = 5
5 = 5이런 문제에서는 start와 end를 사용해 현재 구간의 합을 관리합니다. 구간 합이 작으면 end를 늘리고, 구간 합이 크면 start를 늘려 조절합니다.
이 방식은 다음 글에서 다룰 슬라이딩 윈도우와도 연결됩니다.
12. 연속 부분합 개수 세기
양수 배열에서 연속 부분합이 target이 되는 경우의 개수를 세어보겠습니다.
int[] arr = {1, 2, 3, 2, 5};
int target = 5;
int start = 0;
int end = 0;
int sum = 0;
int count = 0;
while (true) {
if (sum >= target) {
sum -= arr[start];
start++;
} else if (end == arr.length) {
break;
} else {
sum += arr[end];
end++;
}
if (sum == target) {
count++;
}
}
System.out.println(count);출력 결과는 다음과 같습니다.
3연속 부분합이 5가 되는 구간은 2+3, 3+2, 5입니다.
같은 방향 투 포인터는 연속 구간의 합을 관리할 때 자주 사용됩니다.
13. 투 포인터와 완전탐색 비교
투 포인터는 완전탐색보다 효율적인 경우가 많습니다. 두 수의 합 문제를 기준으로 비교해보겠습니다.
| 풀이 방식 | 아이디어 | 시간복잡도 |
|---|---|---|
| 완전탐색 | 모든 두 수 조합 확인 | O(N²) |
| 투 포인터 | 정렬 후 양쪽에서 포인터 이동 | O(N) |
단, 투 포인터를 사용하기 위해 정렬이 필요하다면 정렬 비용 O(N log N)이 추가됩니다. 그래도 이중 반복문 O(N²)보다 훨씬 효율적인 경우가 많습니다.
정렬 O(N log N) + 투 포인터 O(N)
→ 전체 O(N log N)14. 투 포인터가 사용되는 대표 문제
투 포인터는 아래와 같은 문제에서 자주 사용됩니다.
| 문제 유형 | 설명 |
|---|---|
| 두 수의 합 | 정렬된 배열에서 합이 target인 쌍 찾기 |
| 세 수의 합 | 하나를 고정하고 나머지 두 수를 투 포인터로 탐색 |
| 가장 가까운 합 | target과의 차이가 가장 작은 조합 찾기 |
| 연속 부분합 | start와 end로 구간 합 관리 |
| 중복 제거 | 정렬 배열에서 서로 다른 값만 유지 |
문제를 보고 정렬된 배열에서 양쪽 값을 비교하거나, 연속 구간을 조절해야 한다면 투 포인터를 떠올려볼 수 있습니다.
15. 투 포인터에서 자주 하는 실수
투 포인터 문제를 풀 때는 아래 실수를 조심해야 합니다.
- 정렬이 필요한 문제인데 정렬하지 않는 경우
- 정렬하면 원래 인덱스가 사라지는 문제를 고려하지 않는 경우
- sum이 target보다 작을 때와 클 때 포인터 이동 방향을 반대로 하는 경우
- left와 right가 같은 위치를 가리키는 경우를 허용하는 경우
- while 조건을 잘못 작성해서 무한 반복이 발생하는 경우
- 합을 찾은 뒤 포인터를 이동하지 않는 경우
- 중복 값이 있을 때 중복 처리를 하지 않는 경우
특히 두 수를 골라야 하는 문제에서는 같은 원소를 두 번 사용하면 안 됩니다. 그래서 보통 조건을 left < right로 작성합니다.
while (left < right) {
// 서로 다른 두 원소 사용
}투 포인터에서는 포인터 이동 조건을 잘못 잡으면 정답을 놓치거나 무한 반복이 생길 수 있습니다.
16. 정리
이번 글에서는 투 포인터에 대해 정리했습니다.
- 투 포인터는 두 개의 위치 변수를 이용해 탐색하는 기법이다.
- 정렬된 배열에서 두 수의 합을 찾을 때 자주 사용된다.
- 합이 작으면 left를 이동해 값을 키우고, 합이 크면 right를 이동해 값을 줄인다.
- 양쪽 끝에서 좁히는 방식과 같은 방향으로 이동하는 방식이 있다.
- 완전탐색 O(N²)을 O(N) 또는 O(N log N) 수준으로 줄일 수 있는 경우가 많다.
- 연속 부분합 문제에서는 start와 end를 이용해 구간을 관리한다.
- 포인터 이동 기준과 종료 조건을 정확히 잡는 것이 중요하다.
- 정렬이 필요한지, 원래 인덱스가 필요한지 먼저 확인해야 한다.
투 포인터는 처음에는 포인터 이동 방향이 헷갈릴 수 있지만, 정렬된 배열에서 합을 키울지 줄일지를 기준으로 생각하면 훨씬 이해하기 쉽습니다.
투 포인터의 핵심은 두 위치를 움직이면서 불필요한 탐색을 줄이고 조건을 만족하는 구간이나 값을 찾는 것입니다.
다음 글 예고
다음 글에서는 슬라이딩 윈도우에 대해 알아보겠습니다.
고정 길이 또는 가변 길이 구간을 이동시키며 합, 개수, 최댓값, 조건 만족 구간을 효율적으로 구하는 방법을 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 38. 누적합(Prefix Sum) (0) | 2026.07.21 |
|---|---|
| [알고리즘] 37. 슬라이딩 윈도우 (0) | 2026.07.20 |
| [알고리즘] 35. Comparator 완전 정복 (0) | 2026.07.18 |
| [알고리즘] 34. Java 정렬 사용법 (0) | 2026.07.17 |
| [알고리즘] 33. 정렬 알고리즘 개념 (0) | 2026.07.16 |