투포인터

✅ 투 포인터(Two Pointers) 개념
투 포인터(Two Pointers) 기법은 두 개의 포인터(변수)를 활용하여 특정 조건을 만족하는 값을 빠르게 찾는 알고리즘 기법입니다.
주로 정렬된 배열 또는 슬라이딩 윈도우 문제에서 활용됩니다.

📌 투 포인터 활용 방식
두 개의 포인터를 사용하여 문제를 해결
한 개는 시작 지점, 다른 하나는 끝 지점에서 출발하거나 특정 조건에 맞춰 움직임
한쪽 포인터를 이동시키며 탐색하여 원하는 결과를 찾음
O(N) 또는 O(NlogN) 시간복잡도로 최적화 가능
✅ 투 포인터 예제 문제 1: 두 수의 합 (Two Sum)
📌 문제
정렬된 배열이 주어졌을 때, 두 수의 합이 특정 target 값이 되는 인덱스를 찾으시오.

📌 해결 방법
왼쪽 포인터 left 는 0에서 시작
오른쪽 포인터 right 는 N-1에서 시작
arr[left] + arr[right] 값이 target보다 크면 right 감소
arr[left] + arr[right] 값이 target보다 작으면 left 증가
두 수의 합이 target이면 정답

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum == target) {
            return {left, right}; // 정답 인덱스 반환
        } 
        else if (sum < target) {
            left++; // 더 큰 값을 만들기 위해 left 증가
        } 
        else {
            right--; // 더 작은 값을 만들기 위해 right 감소
        }
    }

    return {-1, -1}; // 못 찾으면 -1 반환
}

int main() {
    vector<int> arr = {1, 2, 3, 5, 8, 11, 15};
    int target = 10;

    vector<int> result = twoSum(arr, target);

    if (result[0] != -1)
        cout << "두 수의 인덱스: " << result[0] << ", " << result[1] << endl;
    else
        cout << "해당하는 두 수 없음" << endl;

    return 0;
}

✅ 시간복잡도: O(N)
right 포인터가 N번 순회하고, left도 N번 이동 가능하므로 최악의 경우 O(2N) ≈ O(N)으로 동작합니다.

✅ 투 포인터 활용 정리
문제 유형 설명 시간복잡도
두 수의 합 정렬된 배열에서 합이 target인 두 수 찾기 O(N)
연속 부분합 연속된 부분 배열의 합이 target 이상이 되는 최소 길이 찾기 O(N)
정렬된 배열에서 중복 제거 정렬된 배열에서 중복을 제거하여 유니크한 원소 찾기 O(N)
두 배열 병합 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열 만들기 O(N)
➡️ 투 포인터는 정렬된 배열과 부분합 문제에서 자주 쓰이며, 효율적으로 O(N) 시간 복잡도로 해결이 가능! 🚀