알고리즘 - 투 포인터

투 포인터

---

투 포인터(Two Pointers) 기법은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘 설계 방법이다. 이 기법은 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 부분 배열이나 쌍을 찾는 문제를 풀 때 자주 활용된다.

투 포인터는 주로 다음과 같은 상황에서 유용하다:

- 두 요소의 합이나 곱과 관련된 조건을 만족하는 쌍을 찾는 경우
- 특정 조건을 만족하는 부분 배열의 길이, 개수 등을 구하는 경우
- 슬라이딩 윈도우와 함께 사용하여 효율적으로 부분합을 계산하는 경우

투 포인터의 동작 원리

---

1. 초기화: 두 개의 포인터를 각각 배열의 시작과 끝에 두거나, 특정 조건에 맞게 시작점을 설정한다.
2. 조건 검토 및 이동: 조건에 따라 포인터를 이동시킨다. 일반적으로 한 포인터는 증가하고, 다른 하나는 감소하거나 고정된다.
3. 결과 계산: 각 단계에서 조건을 만족하는 경우 결과를 계산하거나 특정 동작을 수행한다.
4. 종료: 두 포인터가 배열의 끝을 초과하거나 서로 교차하면 알고리즘을 종료한다.

장점

- 배열을 처음부터 끝까지 순회하지 않고, 일부 구간만 탐색하므로 시간 복잡도를 줄일 수 있다.
- 간단한 구현으로도 효율적인 결과를 얻을 수 있다.

단점

- 배열이 정렬되어 있어야 하는 경우가 많아, 정렬되지 않은 배열에 대해 사전 정렬 작업이 필요할 수 있다.
- 특정 문제에 대한 사용 가능성이 제한적이다.

 

예제 코드 분석: 부분합이 m인 경우의 수 구하기

문제 설명

주어진 배열에서 부분합이 m인 경우의 수를 구하는 문제를 투 포인터를 이용해 해결한다. 예를 들어, 배열 [1, 2, 3, 2, 5]에서 m=5일 때, 부분합이 5가 되는 부분 배열은 [2, 3]과 [5]로 총 두 가지이다.

코드 분석

  

    
    
    
    
  
public class Tpointer {
	static int n, m;
	static int arr[];
	public static void main(String[] args) throws IOException{  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

    	StringTokenizer st = new StringTokenizer(br.readLine());  

    	n = Integer.parseInt(st.nextToken());  
    	m = Integer.parseInt(st.nextToken());  

    	arr = new int[n];  

    	st = new StringTokenizer(br.readLine());  
    	for(int i = 0; i < n; i++){  
        	arr[i] = Integer.parseInt(st.nextToken());  
    	}  

    	int start = 0, end = 0, sum = 0, res = 0;  
    	while(true) {  
        	if(sum >= m) {  
            	sum -= arr[start++];  
        } else if (end == n) {  
            break;  
        } else if (sum < m) {  
            sum += arr[end++];  
        }  
        if (sum == m) res++;  
    }  
    Syste.out.print(res);
}

주요 구현 내용

초기 변수 설정:

• start와 end는 각각 부분 배열의 시작과 끝을 나타내는 포인터이다.
• sum은 현재 부분 배열의 합을 저장하는 변수이다.
• res는 조건을 만족하는 부분 배열의 개수를 저장한다.

1. 투 포인터 루프:
   • sum >= m일 때: 부분합이 목표값 이상이므로, start 포인터를 오른쪽으로 이동시켜 구간을 좁힌다.
   • end == n일 때: 배열의 끝에 도달했으므로 루프를 종료한다.
   • sum < m일 때: 부분합이 목표값 미만이므로, end 포인터를 오른쪽으로 이동시켜 구간을 확장한다.
2. 조건 만족 시 결과 계산:
   • sum == m이면 현재 부분 배열이 조건을 만족하므로, res를 증가시킨다.
3. 종료 조건:
   • end가 배열의 끝까지 도달한 경우 루프를 종료한다.

동작 과정 예시

배열: [1, 2, 3, 2, 5], 목표 값 m=5

start	end	부분 배열	sum	res
0	2	[1, 2]	3	0
0	3	[1, 2, 3]	6	0
1	3	[2, 3]	5	1
2	4	[3, 2]	5	2
3	5	[2, 5]	7	2
4	5	[5]	5	3

최종적으로 조건을 만족하는 부분 배열의 개수는 3이다.

 

 

결론

투 포인터 기법은 배열에서 특정 조건을 만족하는 구간을 빠르게 찾는 데 매우 유용한 알고리즘이다. 본 코드에서는 투 포인터를 활용하여 부분합이 특정 값과 일치하는 구간의 개수를 효율적으로 구할 수 있었다. 이러한 방법은 시간 복잡도를 O(n)으로 줄이며, 특히 입력 데이터가 크거나 실시간 처리 요구가 있는 경우에 큰 이점을 제공한다.