투포인터 기법

이 글은 알고리즘에서 투포인터 기법에 대해 공부한 것을 정리한 내용을 다루고 있습니다.

투포인터 기법

투포인터 기법은 배열이나 리스트와 같은 자료구조에서 두 개의 포인터를 이용해서 특정 조건을 만족하는 값을 찾거나 계산하는 알고리즘 기법이다. 보통 정렬된 배열에서 많이 사용되는데, 두 포인터를 적절히 이동시키면서 원하는 값을 찾아가는 방식으로 시간 복잡도를 줄여주는 데 큰 도움이 된다.

간단한 설명

1. 두 개의 포인터를 사용해서 문제를 푼다.
2. 각 포인터는 배열의 다른 위치에 놓인다.
3. 두 포인터를 적절히 이동시키면서 원하는 값을 찾는다.
   예제:
   다음은 정렬된 배열에서 두 수의 합이 특정 값 target이 되는 경우를 찾는 예제야.

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

bool twoPointerSum(const vector<int>& arr, int target) {
    int left = 0; // 첫 번째 포인터
    int right = arr.size() - 1; // 두 번째 포인터

    while (left < right) {
        int sum = arr[left] + arr[right];
        
        if (sum == target) {
            return true; // 두 수의 합이 target과 같으면 true 리턴
        } else if (sum < target) {
            left++; // 합이 target보다 작으면 left 포인터를 증가시켜
        } else {
            right--; // 합이 target보다 크면 right 포인터를 감소시켜
        }
    }
    return false; // 두 수의 합이 target과 같지 않으면 false 리턴
}

int main() {
    vector<int> arr = {1, 3, 4, 6, 8, 10};
    int target = 10;

    if (twoPointerSum(arr, target)) {
        cout << "두 수의 합이 " << target << "인 경우가 존재해!" << endl;
    } else {
        cout << "두 수의 합이 " << target << "인 경우는 없어." << endl;
    }

    return 0;
}

설명

• arr은 정렬된 배열이고, target은 우리가 찾고자 하는 두 수의 합임
• left 포인터는 배열의 맨 앞에서 시작하고, right 포인터는 배열의 맨 끝에서 시작
• 두 포인터가 가리키는 값의 합이 target과 같으면 true를 리턴하고, 그렇지 않으면 합에 따라 포인터를 이동시키며 반복

시간 복잡도

• 배열이 정렬되어 있다고 가정하면, 투포인터 기법을 사용한 이 알고리즘은 O(N)의 시간 복잡도를 가짐.