[C++/Algorithm] 투 포인터, 구간 합 이해하기

만약에 문제에서 연속된 데이터 구간을 처리하기를 원한다면

 

투 포인터 혹은 구간 합을 활용하여 O(n)의 시간 복잡도로 해결할 수 있습니다.

 

 

1. 투 포인터

 

{1, 2, 3, 2, 5} 의 배열이 있고, 연속된 수열의 합이 5인 수열의 개수를 묻는 문제가 있을 수 있습니다.

 

이러한 문제는 시간에 제한이 없다면 간단하게 for 루프를 중첩시켜 O(n^2)에 해결하는 방법이 있을 수 있습니다.

 

하지만 인풋 사이즈와 시간 제한으로 인해 O(n^2)의 알고리즘을 사용할 수 없는 경우라면 어떻게 해야 할까요?

 

 

 

그림과 같이 첫 점을 가리키는 두개의 포인터를 선언했다고 가정해 볼게요. 이 상태에서 합이 5 이상이 될 때까지 sum이라는 변수에 값들을 더해주며 End pointer를 우측으로 이동하여 줍니다.

 

 

자 Sum이 5를 초과하였습니다. 그러면 저희는 Sum=5인 수열을 찾고 있기 때문에 Start pointer를 증가시켜주고, Sum에서 현재 Start pointer가 가리키는 점의 값을 빼줍니다.

 

 

 

Sum이 5가 되었습니다. 이제 결과에 1을 추가해줍니다. {2, 3} 이라는 수열은 저희가 찾는 수열입니다. 

 

그리고 다음 경우를 찾기 위해 End pointer를 한칸 이동해줍니다.

 

누적 합 값이 7로 저희가 원하는 5보다 큽니다. 이 경우 Start pointer를 증가시켜줍니다.

 

하나의 경우의 수를 다시 찾았습니다. 

 

이제 End pointer를 다시 한칸 옮겨 줍니다.

 

다시 합이 5를 초과하였습니다. Start pointer를 줄여줍니다.

 

아직 합이 5가 초과되었으므로 Start pointer를 한 칸 증가시킵니다. 

 

그러면 마지막 경우의 수가 추가되고 답은 3이 나옵니다.

 

 

알고리즘을 요약하면 다음과 같습니다.

 

1. Start pointer, End pointer를 각각 첫 인덱스를 가리키게 설정한다.

2. 현재 누적합이 원하는 값과 같다면 결과값을 증가시킨다.

3. 누적 합이 원하는 값보다 작거나 같으면 End pointer를 한 칸 이동시킨다.

4. 누적 합이 원하는 값보다 크다면 Start pointer를 한칸 이동시킨다.

2 ~ 4 반복

 

우리는 위의 방법으로 O(n)의 시간복잡도에 주어진 문제를 해결할 수 있습니다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int arr[5] = {1, 2, 3, 2, 5};
	
	int s = 0, e = 0;
	int res=0, sum=0;

	for(s = 0; s < 5; s++) {
		while(sum < 5 && e < 5) {
			sum += arr[e];
			e++;
		}
		if(sum==5)	res++;
		sum-=arr[s];
	}
	cout << res << endl;
	return 0;
}

 

 

2. 구간 합

 

만일 위의 예제를 조금 바꾸어서, 매번 시작 인덱스와 끝 인덱스를 주어진다 했을 때 그 합을 묻는 문제가 있을 수 있습니다.

 

만약 

위와 동일한 배열 {1, 2, 3, 2, 5}에서 

1 ~ 3의 구간 합, 1 ~ 4의 구간 합, 2 ~ 4의 구간 합 등등 계속하여 묻는다면 어떻게 해결할까요?

 

우리는 그러할 때 구간 합이라는 것을 활용할 수 있습니다.

 

이러한 배열이 주어진다면 우리는 새로운 배열을 다음과 같이 만들 수 있습니다.

 

2번 인덱스에 1~2까지의 합, 3번 인덱스에 1~3번까지의 합... 이런 식으로 계속 구해 나갑니다.

 

당연하게도 이 배열을 만드는 데에 걸리는 시간복잡도는 O(n)입니다.

 

왜냐하면 새로운 배열의 i번째 인덱스는 다음의 식으로 구할 수 있기 때문입니다. new_arr[i] = new_arr[i-1] + arr[i]

 

이제 1 ~ 3의 구간 합, 1 ~ 4의 구간 합, 2 ~ 4의 구간 합을 다음과 같이 구할 수 있습니다.

new_arr[3], new_arr[4], new_arr[4]-new_arr[1]

 

직관적으로 이해가 가시나요?

 

2 ~ 4의 구간 합은 0~4까지의 합 - 0~1까지의 합이기 때문에 위의 식이 각각 성립하는 것입니다.

 

우리는 다음과 같은 방법으로 특정 구간에 대한 쿼리를 효율적으로 처리할 수 있습니다.

 

(추가로 i-1에 대한 처리 부분이 있기 때문에 배열을 1번 인덱스부터 사용하시는 것이 문제를 효율적으로 풀 수 있습니다.)

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int arr[6] = {0, 1, 2, 3, 2, 5};
	int presum[6];
	
	presum[0] = arr[0];
	for (int i = 1; i < 5; i++)	presum[i] = presum[i-1] + arr[i];
	
	cout << presum[3] << endl;
	cout << presum[4] << endl;
	cout << presum[4]-presum[1] << endl;
	return 0;
}