배열을 다루는 코딩 테스트 문제에서 "시간 초과(Time Limit Exceeded)"를 해결하는 구세주 같은 알고리즘이 있습니다. 바로 투 포인터(Two Pointers)입니다. 이름 그대로 '두 개의 포인터(화살표)'를 사용하여 배열을 훑는 기법입니다. 보통 이중 반복문(For문 안에 For문)을 써서 $O(N^2)$이 걸리는 문제를, 단 한 번의 스캔인 $O(N)$으로 끝내버리는 마법 같은 최적화 기술입니다. 오늘은 투 포인터의 핵심 원리를 직관적인 예시를 통해 알아보겠습니다.
1. 투 포인터란 무엇인가?
우리가 책을 읽을 때 보통 손가락 하나로 글자를 짚어가며 읽습니다. 하지만 투 포인터는 왼손 검지와 오른손 검지, 두 개의 손가락을 동시에 사용하여 데이터를 가리키는 방식입니다. 이 두 개의 포인터가 움직이는 방식에 따라 크게 두 가지 유형으로 나뉩니다.
- 양 끝에서 조여오기: 정렬된 배열에서 두 수의 합 찾기 등에 사용됩니다. (Start -> , <- End)
- 슬라이딩 윈도우 (같이 가기): 특정 구간의 합이나 부분 수열을 구할 때 두 포인터가 같은 방향으로 이동합니다. (Start -> , End ->)
2. 대표 예제: 정렬된 배열에서 두 수의 합 찾기
문제: `[1, 3, 5, 7, 9, 11, 15]`라는 정렬된 배열이 있습니다. 합해서 `20`이 되는 두 숫자의 인덱스를 찾으시오.
2-1. 비효율적인 방법 (이중 반복문)
첫 번째 숫자 1을 잡고 나머지 3, 5, 7... 다 더해봅니다. 없으면 3을 잡고 또 다 더해봅니다. 이렇게 하면 $N \times N$번의 계산이 필요합니다. 데이터가 10만 개라면 100억 번 연산해야 하므로 너무 느립니다.
2-2. 투 포인터 해결법
1. 왼쪽 포인터(L)는 맨 처음(1), 오른쪽 포인터(R)는 맨 끝(15)을 가리킵니다. 2. 현재 합: `1 + 15 = 16`. 목표인 20보다 작습니다. 3. 합을 키워야 하므로, 작은 값을 가리키는 L을 오른쪽으로 한 칸 이동시킵니다. (값 3) 4. 현재 합: `3 + 15 = 18`. 여전히 20보다 작습니다. L 이동. (값 5) 5. 현재 합: `5 + 15 = 20`. 찾았다!
만약 합이 목표보다 컸다면, 큰 값을 줄이기 위해 R을 왼쪽으로 이동시키면 됩니다. 이 방식은 L과 R이 서로 만날 때까지만 진행되므로, 배열을 딱 한 번만 훑게 되어 속도가 엄청나게 빠릅니다.
3. 슬라이딩 윈도우 (Sliding Window)
투 포인터의 응용으로, "연속된 부분 배열의 합이 S 이상인 가장 짧은 길이 구하기" 같은 문제에 쓰입니다. 두 포인터 사이의 간격을 창문(Window)이라고 생각하고, 이 창문을 옆으로 밀면서(Sliding) 창문 안의 값들을 계산하는 방식입니다. 매번 처음부터 다시 더하는 게 아니라, "새로 들어온 값은 더하고, 빠지는 값은 뺀다"는 아이디어로 연산량을 획기적으로 줄입니다.
1. 투 포인터는 두 개의 인덱스를 조작하여 배열을 1회 스캔(O(N))만으로 탐색하는 기법입니다.
2. 이중 반복문으로 인한 $O(N^2)$ 시간 복잡도를 $O(N)$으로 최적화할 때 주로 사용됩니다.
3. 정렬된 배열에서의 합 찾기, 연속된 구간의 합 구하기 등에서 필수적인 알고리즘입니다.