투포인터

투 포인터(Two Pointers) 알고리즘은 배열 또는 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 구간을 찾거나 원하는 값을 찾는 알고리즘 기법입니다. 이 알고리즘은 주로 배열 또는 리스트가 정렬되어 있을 때 효과적으로 사용됩니다. 투 포인터 알고리즘은 시간 복잡도 O(N)에 효율적으로 동작할 수 있어 많은 문제에 유용하게 쓰입니다.

주로 정렬된 배열이나 리스트에서 사용되며, 배열의 시작과 끝을 가리키는 두 개의 포인터를 사용합니다.
두 개의 포인터는 시작 지점과 끝 지점을 가리키고, 이 두 포인터를 이용하여 구간을 좁혀나가거나 특정 조건을 만족시킬 때까지 이동합니다.

그림과 같이 Left와 Right 라는 포인터를 지정해주고 하나 씩 이동해가며 조건에 맞는 값을 찾습니다.

백준 1644 소수의 연속합

list 라는 배열을 이용하여 투포인터를 구현한 코드입니다.
Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();
		boolean[] v= new boolean[N+1];
		if(N==1) {
			System.out.println(0);
			return;
		}
		v[0]=true; v[1]=true;
		for(int i=2;i*i<=N;i++) {
			if(!v[i]) {
				for(int j=2*i;j<=N;j+=i) v[j]=true;
			}
		}
		for(int i=1;i<=N;i++) {
			if(!v[i]) list.add(i);
		}
		int start=0;
		int end =0;
		int sum=list.get(start);
		
		
		while(end<list.size()&&start<=end) {
			if(sum==N) {
				sum-=list.get(start);
				start++;
			}
			else if(sum<N) {
				end++;
				if(end>=list.size()) break;
				sum+=list.get(end);
			}
			else {
				sum-=list.get(start);
				start++;
			}
		}
		System.out.println(res);
	}
}