투 포인터 알고리즘은 알고리즘 문제 풀이에서 자주 사용되는 기법입니다.
선형 자료구조(배열, 문자열 등)에서 특정 조건을 만족하는 부분을 빠르게 찾을 수 있습니다.
이번 포스트에서는 투 포인터 알고리즘에 대해 자세히 알아보겠습니다.
Table of Contents
투 포인터 알고리즘이란?
이는 두 개의 포인터를 사용해 배열을 탐색하는 방식입니다.
- 배열에서 부분합, 부분 구간, 특정 쌍 탐색에 자주 쓰입니다.
- 일반적으로 정렬된 배열이나 조건이 연속된 데이터에 사용하면 좋습니다.
기본 개념
포인터란?
- 배열의 위치를 가리키는 변수입니다. 예: left, right, start, end, i, j 등
- 배열의 index를 가리키는 변수로 이해하면 됩니다.
투 포인터 구조
- 포인터를 두 개 사용해 배열을 두 부분으로 나누거나 두 위치에서 동시에 탐색을 진행합니다.
대표적인 구조는 다음과 같습니다:
let left = 0;
let right = 0;
while (right < arr.length) {
if (조건이 맞으면) {
left += 1; or right += 1;
} else {
right += 1;
}
}큰 흐름은 배열을 처음부터 탐색하는데 조건이 맞으면 좌우 포인터를 조정하고 조건이 맞지 않으면 알고리즘 종료를 위해 오른쪽 포인터를 이동시키는 것 입니다.
사용 예제
예제 1: 정렬된 배열에서 두 수의 합 찾기
문제: 정렬된 배열 arr에서 합이 target이 되는 두 수를 찾아라.
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right]; // 또는 [arr[left], arr[right]]
} else if (sum < target) {
left++;
} else {
right--;
}
}
return null;
}
console.log(twoSum([1, 2, 3, 4, 6], 7)); // 출력: [1, 4] (2 + 5)배열이 정렬되어 있으므로 left를 오른쪽으로, right를 왼쪽으로 조정하면서 찾을 수 있습니다.
예제 2: 연속된 수들의 합이 특정 값이 되는 부분 구간 찾기 (슬라이딩 윈도우)
문제: 자연수로 이루어진 배열에서 연속된 부분 수열 중 합이 target인 구간의 개수를 구하라.
function countSubarraysWithSum(arr, target) {
let left = 0;
let right = 0;
let sum = 0;
let count = 0;
while (right < arr.length) {
sum += arr[right];
while (sum > target && left <= right) {
sum -= arr[left];
left++;
}
if (sum === target) {
count++;
}
right++;
}
return count;
}
console.log(countSubarraysWithSum([1, 2, 3, 2, 5], 5)); // 출력: 2 ([2,3], [5])위의 예제와 같이 투 포인터 알고리즘의 서브 카테고리인 슬라이딩 윈도우 알고리즘을 사용하면 연속된 구간에서의 조건을 찾을 수 있습니다.
투 포인터가 유용한 상황
- 정렬된 배열에서 특정 쌍 찾기: Two Sum 문제
- 부분합 구간 찾기: 부분 수열의 합이 특정값이 되는 구간 찾기
- 슬라이딩 윈도우: 일정한 크기의 구간을 탐색할 때
- 중복 제거, 중복 카운팅: 서로 다른 문자 조합 찾기 등
- 두 배열 병합: 병합 정렬(Merge Sort)의 핵심 과정
투 포인터 시간복잡도
보통 O(N) 입니다.
- 두 포인터는 각자 최대 한 번씩만 배열을 끝까지 탐색하므로 전체 탐색 시간은 선형입니다.
- 이 덕분에 브루트포스 O(N²) 대신 O(N)으로 문제 해결이 가능합니다.
자주하는 실수
- 포인터가 겹치는 조건을 놓침: while 조건에서 left <= right or left < right를 헷갈림
- 정렬이 안 된 배열에 적용: 정렬이 안 된 배열에서 두 수의 합을 찾으려면 해시맵이 더 적합
- 무한 루프: 포인터 이동 조건을 잘못 작성하여 루프 종료 못함
투 포인터 정리
- 두 개의 인덱스를 사용하여 배열을 효율적으로 탐색하는 알고리즘
- 조건을 만족할 때마다 포인터를 움직이고 전체 시간복잡도는 O(N) 수준
- 다양한 문제에서 활용 가능: Two Sum, 부분합, 슬라이딩 윈도우, 정렬된 배열 병합 등