투포인터 알고리즘(Two-Pointer Algorithm)이란? (예시,활용코드)

Two Pointer 알고리즘이란 1차원 배열에서 두개의 포인터를 활용하여 원하는 결과를 얻기 위한 알고리즘입니다.

 

보통 연속된 수의 합이 충족하는 갯수를 구하게 되는데 dfs로 풀게 되면 엄청난 시간복잡도를 야기하게 됩니다.

 

이를 위해 1차원 배열에서 두개의 포인터를 이용하여 경우의 수에 대해서 마지막에 도달할 경우 값을 구할 수 없어 종료를 시키게 합니다. 시간 복잡도는 O(n)으로 굉장히 알고리즘 문제에서 가끔씩 사용하게 됩니다.

 

예시의 이해를 위해 우리가 주어진 1차원 배열에서 합이 6인 숫자들의 케이스를 모두 카운팅하는 것에 대해서 예시를 들어보겠습니다.

 

 

배열 예시 [1,2,3,3,6,5,1]

원하는 합이 6이 되는 연속된 숫자들의 조합 갯수

 

투포인터 활용 설명

 

합이 6보다 작을때는 end의 인덱스를 증가시킵니다.

합이 6보다 크거나 같을때는 start의인덱스를 증가 시킵니다.

 

위의 조건을 반복하면서 end인덱스가 arr의 size에 도달할 경우 반복문을 종료합니다.

 

c++로 구현한 코드

#include <iostream>

#include <vector>

int count_combinations(const std::vector<int>& arr, int target) {

    int count = 0;

    int left = 0;

    int right = 0;

    int current_sum = arr[0];

    while (right < arr.size()) {

        if (current_sum < target) {

            right++;

            if (right < arr.size()) {

                current_sum += arr[right];

            }

        } else if (current_sum > target) {

            current_sum -= arr[left];

            left++;

        } else {

            count++;

            current_sum -= arr[left];

            left++;

        }

    }

    return count;

}

int main() {

    std::vector<int> arr = {1, 2, 3, 3, 6, 5, 1};

    int target = 6;

    int combinations = count_combinations(arr, target);

    std::cout << "조합의 개수: " << combinations << std::endl;

    return 0;

}

 

 

투포인터 관련 알고리즘 문제 추천

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

https://bendeng-life.tistory.com/129

[프로그래머스 보석 쇼핑] c++ (풀이,코드, 투포인터 알고리즘)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합