[알고리즘] 투 포인터와 부분합

투포인터란?

"정렬된" 리스트 상에서 두 개의 포인터(= index 좌표) 를 사용하여 순차적으로 접근하면서 구간의 값이 목표 값과 같을 때까지 포인터를 조작하며 원하는 부분합과 구간을 구할 수 있는 알고리즘 기법입니다.

 

투 포인터는 주로 1차원 배열 상에서 부분합 등을 구할 때 주로 사용하게 되는데요.

이때 무조건 1차원 배열이라고 해서 투포인터를 사용할 수 있는 것은 아니며,

배열이 정리되어 있지 않다면 정렬된 상태로 만들어 주어야 합니다.

 

투포인터는 O(N)의 시간 복잡도를 가집니다.

 

알고리즘 설명

정렬된 값을 가지는 1차원 배열이 주어지고, K라는 값을 가지는 배열 속 숫자들의 부분합을 구한다고 가정해보겠습니다.

이 경우 투포인터를 사용하면 아래와 같이 포인터의 이동을 표현할 수 있는데요.

 

Fig 1.0. 투포인터의 이동

배열의 첫 번째 인덱스에 나란히 놓인 두 개의 포인터는 가리키고 있는 두 점 사이에 부분합을 기준으로 이동하게 됩니다.

부분합 sum이 목표 값 K 보다 작다면, 부분합의 크기를 늘려주어야 하므로 오른쪽 포인터 right를 이동시켜 줍니다.

위의 동작은 부분합 sum이 K보다 크거나 같을 때까지 반복하여 수행합니다.

 

부분합 sum이 K보다 크커나 같아지면 이제 왼쪽 포인터의 크기를 한 칸씩 이동시켜줍니다.

단, 이 때 왼쪽 포인터는 부분합이 목표 값 K 보다 클 경우에 이동하며,

만약 오른쪽 포인터가 끝에 도달했다면 왼쪽 포인터도 끝에 도달할 때까지 포인터가 이동합니다.

 

이러한 두 가지 동작을 두 포인터가 배열을 모두 순회할 때까지 반복하는 것이 투포인터 알고리즘의 특징입니다.

 

두 포인터가 이동함에 따라 각각의 부분합과, 좌표의 이동을 그림으로 표현하면 아래와 같습니다.

 

Fig 1.1. 투포인터의 이동에 따른 부분합과 좌표

찾고자 하는 목표 값 K 가 7이고,

1부터 5까지 정렬된 배열이 주어졌다고 했을 때,

투 포인터가 어떻게 이동하는지 표로 정리 하면 위의 그림과 같습니다.

 

직접 모든 경우 마다 좌표와 부분합을 기록해보았을 때,

오른쪽 포인터가 먼저 이동하고 이어서 왼쪽, 오른쪽 번갈아가며 좌표가 이동하는 것을 확인할 수 있네요.

 

이를 소스코드로 작성해본다면 아래와 같이 작성할 수 있습니다.

 

소스코드

int left = 0;
int right = 0;
int sum = sequence[left];
int L = sequence.length;

while(true) {			
    if(left < L && right < L && sum == k) {
    	System.out.println("left = "+left+", right = "+right+", sum = "+sum;
    }			
    
    if(left >= L && right >= L) break;	// 두 포인터 모두 끝에 도달하면 반복 종료
    
    if(sum < k && right < L) {
        right++;
        if(right < L ) sum += sequence[right];
    }else {
        if(left < L) sum -= sequence[left];
        left++;
    }			
}

 

---

 

 

 

📌 함께 풀어보면 좋은 문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스