[c++/알고리즘] 투포인터

시간복잡도 : O(n)

​

투포인터는 1차원 배열에서 두개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다.

두개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있다. 

​

투포인터는 start와 end라는 두개의 포인터를 사용한다.

start는 부분배열의 앞 쪽을 가르키는 인덱스이며 end는 부분배열의 뒤 쪽을 가르키는 인덱스이다.

두개의 포인터는 항상 start<=end를 만족한다. 

 

매 순간마다 부분합 배열의 합과 구해야하는 값을 비교하여 포인터를 이동하게 된다.

• 부분합 배열의 합 < 구해야하는 값

      start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기 증가시킴

 

• 부분합 배열의 합 >= 구해야하는 값

      end를 왼쪽으로 한 칸 이동하여 부분합 배열 크기 감소시킴

while (left < right) {
		if (arr[left] + arr[right] == x) {
			sum += 1;
			left += 1;
			right -= 1;
		}
		else if (arr[left] + arr[right] > x) {
			right -= 1;
		}
		else {
			left += 1;
		}
	}

 

투포인터의 가장 기본적인 문제는 https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스의 구명보트 문제이다.