투 포인터 알고리즘 (TwoPointers)

배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 정렬된 배열에서 특정 조건을 만족하는 부분배열또는 원하는 값을 찾는 등의 문제를 풀 때 주로 사용하는 알고리즘!

 

보통 정렬된 배열에서 두 수의 합찾기,연속된 부분 배열의 합 찾기 에사용

투포인터알고리즘은두개의포인터를사용

●  왼쪽포인터(LeftPointer) : 배열의시작지점에서시작하여오른쪽으로이동

● 오른쪽포인터(Right Pointer):배열의끝지점에서시작하여왼쪽으로이동 또는 왼쪽포인터와함께배열의시작지점에서시작하여오른쪽으로이동

 

#include <bits/stdc++.h> // C++ 표준 라이브러리 헤더
using namespace std;

int n, ret, x; // n: 배열 크기, ret: 조건을 만족하는 쌍의 개수, x: 목표 합

int main() {
    cin >> n; // 배열 크기 입력
    vector<int> a(n); // 크기가 n인 벡터 생성

    // 배열 요소 입력
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cin >> x; // 목표 합 입력

    // 배열을 오름차순으로 정렬
    sort(a.begin(), a.end());

    int l = 0, r = n - 1; // 두 포인터 초기화 (왼쪽 포인터 l, 오른쪽 포인터 r)

    // 투 포인터 알고리즘으로 배열 탐색
    while (l < r) {
        // 두 포인터가 가리키는 값을 더함
        if (a[l] + a[r] == x) { // 두 수의 합이 x와 같은 경우
            r--;     // 오른쪽 포인터 이동
            ret++;   // 조건을 만족하는 쌍의 개수 증가
        } else if (a[l] + a[r] > x) {
            r--;     // 합이 x보다 크면 오른쪽 포인터 감소
        } else if (a[l] + a[r] < x) {
            l++;     // 합이 x보다 작으면 왼쪽 포인터 증가
        }
    }

    cout << ret << "\n"; // 조건을 만족하는 쌍의 개수 출력
}

---

투 포인터 알고리즘 설명

정의

• 투 포인터(Two Pointers) 알고리즘은 정렬된 배열(또는 리스트)에서 두 개의 포인터를 사용하여 특정 조건을 효율적으로 찾는 방법입니다.
• 일반적으로 배열의 양쪽 끝에서 시작하여, 포인터를 이동하면서 탐색합니다.

알고리즘 흐름

1. 포인터 초기화:
   • 왼쪽 포인터 l은 배열의 시작 (0).
   • 오른쪽 포인터 r은 배열의 끝 (n - 1).
2. 조건 확인:
   • a[l] + a[r] 값이 목표 값 x와 비교.
   • a[l] + a[r] == x이면, 조건을 만족하는 경우로 처리.
   • a[l] + a[r] < x이면, 합을 늘리기 위해 왼쪽 포인터를 증가.
   • a[l] + a[r] > x이면, 합을 줄이기 위해 오른쪽 포인터를 감소.
3. 포인터 이동:
   • 조건에 따라 l 또는 r을 이동하여 효율적으로 탐색.

시간 복잡도

• 배열 정렬: O(nlog⁡n)O(n \log n).
• 투 포인터 탐색: O(n)O(n).
• 총 시간 복잡도: O(nlog⁡n)O(n \log n).

---

예제

입력

7
1 2 3 4 5 6 7
9

출력

2

설명

• 배열: [1,2,3,4,5,6,7][1, 2, 3, 4, 5, 6, 7]
• 목표 합: x=9x = 9
• 정렬 후 투 포인터로 탐색:
  1. 1+7=81 + 7 = 8 → l++l++
  2. 2+7=92 + 7 = 9 → 조건 만족, ret++ret++, r−−r--
  3. 2+6=82 + 6 = 8 → l++l++
  4. 3+6=93 + 6 = 9 → 조건 만족, ret++ret++, r−−r--
  5. 3+5=83 + 5 = 8 → l++l++
  6. 4+5=94 + 5 = 9 → 조건 만족, ret++ret++, r−−r--

---

활용 예

• 배열에서 특정 합을 찾기:
  • 두 수의 합 또는 차가 특정 값이 되는 쌍을 찾는 문제.
• 문자열 비교:
  • 두 문자열에서 특정 패턴을 효율적으로 찾을 때.