Two Pointer

투 포인터(Two Pointers) 개념
투 포인터 알고리즘은 배열이나 리스트에서 두 개의 포인터(인덱스)를 활용하여 문제를 해결하는 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나 최적화하는 데 사용된다.

투 포인터의 일반적인 사용처
정렬된 배열에서 두 수의 합 찾기 (Two Sum 문제)

구간(부분 배열) 합 찾기 (Subarray Sum 문제)

두 개의 정렬된 배열 병합 (Merge Two Sorted Arrays)

펠린드롬(회문) 검사

최대 길이의 연속된 부분 구간 찾기

C++ 예제
1. 정렬된 배열에서 두 수의 합 찾기

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

bool 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) {
            cout << "찾은 값: " << arr[left] << " + " << arr[right] << " = " << target << endl;
            return true;
        } else if (sum < target) {
            left++;  // 합이 작으면 왼쪽 포인터 증가
        } else {
            right--; // 합이 크면 오른쪽 포인터 감소
        }
    }
    return false;
}

int main() {
    vector<int> arr = {1, 2, 3, 5, 7, 10, 12};
    int target = 9;

    if (!twoSum(arr, target)) {
        cout << "해당 합을 만족하는 두 수가 없습니다." << endl;
    }
    return 0;
}