[CS]두 포인터(Two Pointer)

두 포인터 : 투 포인터

• 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘
  • 포인터 : 변소라고 생각하면 쉬움
• 두 개의 점의 위치를 기록하며 처리하는 알고리즘
• 원 포인터보다 시간 개선 가능
• 슬라이딩 윈도우와 유사
  • 단 슬라이딩 윈도우는 탐색 과정에서 구간의 넓이가 일정
• 정렬된 두 리스트의 합집합 / 병합정렬의 conquer 영역에 사용
• 시간 복잡도 : $O(N^2)$의 시간 복잡도를 부분배열을 활용해 줄임
  • 최악(worst): $O(2N)$
  • 시간 복잡도: $O(N)$

두 포인터 예제

특정한 합을 가지는 부분 연속 수열 찾기

• 대표적인 투 포인터 문제
• 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제
  1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
  2. 현재 부분 합 = M
  • cnt를 1 증가
  3. 현재 부분 합 < M
  • end를 1 증가 => 부분 합 크기 증가
  4. 현재 부분 합 >= M
  • start를 1 증가 => 부분 합 크기 감소
  5. 모든 경우를 확인할때까지 2 ~ 4번 과정을 반복한다.
• M = 5 리스트 예시
  [1단계] : 시작점과 끝점이 첫번째 원소의 인덱스를 가르키도록 설정
  
  [2단계] : 1(부분합) < 5(M) -> end 증가
  
  [3단계] : 3(부분합) < 5(M) -> end 증가
  
  [4단계] : 6(부분합) >= 5(M) -> start 증가
  
  * ...반복
  [마지막] : 시작점과 끝점이 첫번째 원소의 인덱스를 가르키도록 설정
  

#include <iostream>
usingnamespace std;
int board[10001];
int main()
{
	int N, M;
    cin >> N >> M;
	for (int i = 0; i < N; i++)
    cin >> board[i];
	int answer = 0;
	int start = 0;
	int end = 0;
	int partial_sum = 0;
	while (end <= N) {
		if (partial_sum >= M) partial_sum -= board[start++];
		else if (partial_sum < M) partial_sum += board[end++];
		if (partial_sum == M) answer++;
    }
    cout << answer << "\n";
}