투 포인터 알고리듬(Two Pointer Algorithm)의 원리와 구현 - soo:bak

작성일 :

투 포인터 알고리듬이란?

투 포인터 알고리듬은 배열이나 리스트 같은 선형 구조에서 두 개의 포인터를 사용해 효율적으로 문제를 해결하는 기법입니다.

주로 정렬된 배열이나 연속된 데이터를 다룰 때 유용하며, 두 포인터가 조건에 따라 이동하면서 원하는 결과를 찾습니다.

즉, 두 개의 인덱스(포인터)를 활용해 데이터를 탐색하는데,

이 포인터들은 문제에 따라 같은 방향으로 이동하거나 반대 방향으로 이동합니다.

예를 들어,

  • 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 경우.
  • 문자열에서 특정 조건을 만족하는 부분 문자열을 구하는 경우.

이런 문제들에서 투 포인터는 간단하면서도 효율적인 해결 방법들 중 하나입니다.

투 포인터의 기본 원리


투 포인터 알고리듬은 이름 그대로 두 개의 포인터를 사용해 데이터를 탐색합니다.

이 포인터들은 배열의 시작, 끝, 혹은 특정 위치에서 출발하며,

문제 조건에 따라 이동 방향과 방식이 결정됩니다.

주요 패턴


투 포인터는 크게 두 가지 패턴으로 나뉩니다:

  1. 양 끝에서 시작하는 투 포인터
    • 포인터가 배열의 양 끝에서 시작해 서로를 향해 이동합니다.
    • 정렬된 배열에서 합이나 차를 구하는 문제에 적합합니다.
    • 예: 두 수의 합이 특정 값이 되는 쌍 찾기.

  2. 같은 방향으로 이동하는 투 포인터
    • 두 포인터가 같은 방향으로 이동하며, 보통 슬라이딩 윈도우 형태로 동작합니다.
    • 연속된 구간(부분 배열 또는 문자열)을 탐색할 때 사용됩니다.
    • 예: 특정 합을 만족하는 연속된 구간 찾기.

알고리듬적 접근


투 포인터의 핵심은 효율성입니다.

완전 탐색(브루트 포스) 방식은 시간 복잡도가 \(O(n^2)\) 이상이 될 수 있지만,

투 포인터는 대부분 \(O(n)\) 또는 \(O(n \log n)\)으로 문제를 해결합니다.

양 끝 투 포인터 예시


정렬된 배열에서 두 수의 합이 target이 되는 쌍을 찾기.

  1. 배열이 정렬되지 않았다면 정렬합니다. → \(O(n \log n)\)
  2. 두 포인터 left와 right를 설정합니다:
    • left는 배열의 첫 인덱스(0).
    • right는 마지막 인덱스(n - 1).
  3. 다음 과정을 반복합니다:
    • arr[left] + arr[right]를 계산.
    • 합이 target이면 결과를 반환.
    • 합이 target보다 크면 right를 감소.
    • 합이 target보다 작으면 left를 증가.
  4. left가 right 이상이 되면 종료.


C++ 코드 구현 (양 끝 투 포인터)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

pair<int, int> findPairWithSum(vector<int>& arr, int target) {
  sort(arr.begin(), arr.end());
  int left = 0, right = arr.size() - 1;

  while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return {arr[left], arr[right]};
    if (sum < target) left++;
    else right--;
  }

  return {-1, -1}; // 쌍이 없는 경우
}


같은 방향 투 포인터 예시

배열에서 연속된 부분 배열의 합이 target 이하인 가장 긴 구간의 길이를 구하기.

  1. 두 포인터 start와 end를 0으로 초기화.
  2. 구간 합 currentSum을 유지하며 end를 증가:
    • currentSum에 arr[end]를 더함.
    • currentSum이 target을 초과하면 start를 증가시키며 arr[start]를 뺌.
  3. currentSum이 target 이하일 때 구간 길이(end - start + 1)를 갱신.
  4. 배열 끝까지 반복.


C++ 코드 구현 (같은 방향 투 포인터)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

int maxLengthSubarray(vector<int>& arr, int target) {
  int start = 0, end = 0, currentSum = 0, maxLength = 0;

  while (end < arr.size()) {
    currentSum += arr[end];

    while (currentSum > target && start <= end) {
      currentSum -= arr[start];
      start++;
    }

    maxLength = max(maxLength, end - start + 1);
    end++;
  }

  return maxLength;
}

이렇게 알고리듬 구현은 간단하지만, 다양한 문제에서 굉장히 효율적인 도구로 활용됩니다.

시간 복잡도

투 포인터 알고리듬의 시간 복잡도는 패턴에 따라 다릅니다:

  1. 양 끝 투 포인터:

    • 정렬이 필요하면 \(O(n \log n)\).
    • 정렬된 배열에서는 탐색만 하므로 \(O(n)\).
    • 각 포인터는 최대 \(n\)번 이동.

  2. 같은 방향 투 포인터:

    • 두 포인터가 배열을 한 번씩 순회하므로 \(O(n)\).
    • 각 원소는 상수 시간 내에 처리.


이렇게, 투 포인터 알고리듬은 대규모 데이터에서도 효율적으로 동작합니다.

활용 예시

투 포인터는 다양한 알고리듬 문제에서 효율적으로 사용됩니다 :

  • 두 수의 합: 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾기.
  • 부분 배열/문자열: 연속된 구간에서 특정 조건(합, 길이 등)을 만족하는 구간 탐색.
  • 슬라이딩 윈도우: 가변 크기 윈도우로 데이터 탐색.
  • 기하 문제: 좌표나 벡터의 비율을 단순화하거나 거리 계산.

참고 : 슬라이딩 윈도우(Sliding Window)의 이해와 구현 - soo:bak


또한, 알고리듬 문제가 아닌 실제 실무에서도(예: 문자열에서 특정 패턴 찾기, 데이터 스트리밍에서 특정 시간 내 이벤트를 집계할 때 등) 투 포인터를 활용할 수 있습니다.

주의사항

투 포인터를 사용할 때 주로 주의해야하는 내용은 다음과 같습니다 :

  1. 정렬 여부:
    • 양 끝 투 포인터는 정렬된 배열에서 동작하므로, 정렬이 필요한지 확인.
  2. 포인터 이동:
    • 이동 조건을 잘못 설정하면 무한 루프나 오답이 발생.
  3. 경계 처리:
    • 포인터가 배열 범위를 벗어나지 않도록 주의.
  4. 문제 특성:
    • 배열이나 문자열 같은 선형 구조에 적합하며, 트리나 그래프와 같은 비선형 구조에는 직접 적용하기 어려움.
      (다만, 변형된 형태로 응용 가능합니다.)


마무리

투 포인터 알고리듬은 간단하면서도 효율적인 기법으로, 배열과 문자열 문제를 깔끔하게 해결합니다.

정렬된 데이터나 연속된 구간을 다룰 때 특히 유용하며, 시간 복잡도 \(O(n)\) 또는 \(O(n \log n)\)으로 빠르게 동작합니다.

구현이 직관적이어서 쉽게 익힐 수 있지만, 다양한 문제에 적용 가능한 유연성을 가집니다.

이 블로그의 다른 글