Back to Blog
알고리즘투포인터TwoPointer수고르기부분합

0x14. 투 포인터(Two Pointer) 알고리즘

투 포인터 알고리즘의 개념과 수 고르기, 부분합 문제 풀이를 정리한다.

0x14 투 포인터

배열에서 특정 조건을 만족하는 구간이나 쌍을 찾아야 할 때, 가장 단순한 방법은 이중 for문으로 모든 경우를 탐색하는 것이다. 하지만 이 방식은 O(N^2) 의 시간 복잡도를 가지기 때문에, 배열의 크기가 커지면 시간 초과를 피할 수 없다.

투 포인터(Two Pointer) 는 이 문제를 해결하기 위한 알고리즘이다. 두 개의 포인터를 적절히 이동시키면서 원하는 조건을 탐색하면, 같은 작업을 O(N) 에 처리할 수 있다.

핵심 아이디어는 간단하다. 배열을 정렬한 뒤, 두 포인터가 각각 독립적으로 한 방향으로만 이동하도록 설계하는 것이다. 이렇게 하면 각 포인터가 최대 N번씩만 움직이므로 전체 시간 복잡도가 O(N)이 된다.

0x01 연습 문제 1 - 수 고르기

첫 번째 연습 문제는 수 고르기 문제다. N개의 정수 중에서 두 수를 골라 그 차이가 M 이상이면서 가장 작은 경우를 찾아야 한다.

접근 방식은 다음과 같다. 먼저 배열을 오름차순 정렬한다. 그 다음 시작 포인터 st와 끝 포인터 en을 배열의 맨 앞에 놓고, 두 포인터가 가리키는 값의 차이를 기준으로 포인터를 이동시킨다.

  • 차이가 M보다 작으면 차이를 키워야 하므로 en을 오른쪽으로 이동한다.
  • 차이가 M 이상이면 답 후보로 기록하고, 더 작은 차이를 찾기 위해 st를 오른쪽으로 이동한다.

배열이 정렬되어 있기 때문에, en을 오른쪽으로 옮기면 차이가 커지고 st를 오른쪽으로 옮기면 차이가 작아진다는 성질을 이용하는 것이다.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n, m;
int arr[100002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr+n);

    ll ans = 0x7fffffff;
    int st = 0, en = 0;
    while(st != n - 1 && en < n) {
        ll diff= arr[en] - arr[st];
        if(diff < m) en++;
        else {
            ans= min(ans, diff);
            st++;
        }
    }

    cout << ans << endl;

    return 0;
}

코드를 보면, ans의 초기값을 0x7fffffff(int 최대값)로 설정해서 최솟값 갱신이 자연스럽게 이루어지도록 했다. while 루프 안에서 st와 en은 각각 최대 N번씩만 이동하므로, 전체 시간 복잡도는 정렬의 O(N log N) 이 지배한다.

0x02 연습 문제 2 - 부분합

두 번째 연습 문제는 부분합 문제다. 길이 N인 수열에서 연속된 부분 수열의 합이 S 이상이 되는 것 중, 가장 짧은 길이를 구해야 한다.

이 문제 역시 투 포인터로 접근한다. st와 en이 연속 부분 수열의 시작과 끝을 나타내고, 현재 구간의 합을 기준으로 포인터를 움직인다.

  • 합이 S보다 작으면 구간을 넓혀야 하므로 en을 오른쪽으로 이동한다.
  • 합이 S 이상이면 답 후보로 기록하고, 더 짧은 구간을 찾기 위해 st를 오른쪽으로 이동한다.
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int n, m;
int arr[100002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr+n);

    ll ans = 0x7fffffff;
    int st = 0, en = 0;
    while(st != n - 1 && en < n) {
        ll diff= arr[en] - arr[st];
        if(diff < m) en++;
        else {
            ans= min(ans, diff);
            st++;
        }
    }

    cout << ans << endl;

    return 0;
}

구조는 수 고르기 문제와 거의 동일하다. 투 포인터 문제들은 이처럼 기본 틀이 비슷하고, 포인터를 언제 어떻게 이동시킬지의 조건만 달라지는 경우가 많다. 이 패턴에 익숙해지면 다양한 변형 문제에도 빠르게 대응할 수 있다.

문제 풀이

투 포인터 관련 문제를 추가로 풀게 되면 이 섹션에 정리할 예정이다.

리뷰

투 포인터는 아이디어 자체는 단순하지만, 적용할 수 있는 문제의 범위가 넓다. 정렬된 배열에서 조건을 만족하는 쌍 찾기, 연속 부분 수열의 합, 특정 조건을 만족하는 구간 탐색 등 다양한 유형에 활용된다.

핵심은 두 포인터가 한 방향으로만 이동한다는 점이다. 이 단방향 이동 덕분에 O(N)이 보장되고, 이를 위해서는 보통 배열의 정렬이 선행되어야 한다. 문제를 보고 "이중 for문이 필요한데 시간 초과가 날 것 같다"는 생각이 들면, 투 포인터를 떠올려 보는 것이 좋다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편